article published yes Wolfgang Dvořák author Monika H Henzinger author 540c9bbd-f2de-11ec-812d-d04a5be856300000-0002-5008-6530 David P. Williamson author We study the problem of maximizing a monotone submodular function with viability constraints. This problem originates from computational biology, where we are given a phylogenetic tree over a set of species and a directed graph, the so-called food web, encoding viability constraints between these species. These food webs usually have constant depth. The goal is to select a subset of k species that satisfies the viability constraints and has maximal phylogenetic diversity. As this problem is known to be NP-hard, we investigate approximation algorithms. We present the first constant factor approximation algorithm if the depth is constant. Its approximation ratio is (1−1e√). This algorithm not only applies to phylogenetic trees with viability constraints but for arbitrary monotone submodular set functions with viability constraints. Second, we show that there is no (1−1/e+ϵ)-approximation algorithm for our problem setting (even for additive functions) and that there is no approximation algorithm for a slight extension of this setting. Springer Nature2017 eng Approximation algorithmsSubmodular functionsPhylogenetic diversityViability constraints 0178-4617 1432-0541 1611.0575310.1007/s00453-015-0066-y 771152-172 yes Dvořák, Wolfgang, Monika Henzinger, and David P. Williamson. “Maximizing a Submodular Function with Viability Constraints.” <i>Algorithmica</i>. Springer Nature, 2017. <a href="https://doi.org/10.1007/s00453-015-0066-y">https://doi.org/10.1007/s00453-015-0066-y</a>. Dvořák, Wolfgang, et al. “Maximizing a Submodular Function with Viability Constraints.” <i>Algorithmica</i>, vol. 77, no. 1, Springer Nature, 2017, pp. 152–72, doi:<a href="https://doi.org/10.1007/s00453-015-0066-y">10.1007/s00453-015-0066-y</a>. W. Dvořák, M. Henzinger, and D. P. Williamson, “Maximizing a submodular function with viability constraints,” <i>Algorithmica</i>, vol. 77, no. 1. Springer Nature, pp. 152–172, 2017. Dvořák W, Henzinger M, Williamson DP. 2017. Maximizing a submodular function with viability constraints. Algorithmica. 77(1), 152–172. W. Dvořák, M. Henzinger, D.P. Williamson, Algorithmica 77 (2017) 152–172. Dvořák W, Henzinger M, Williamson DP. Maximizing a submodular function with viability constraints. <i>Algorithmica</i>. 2017;77(1):152-172. doi:<a href="https://doi.org/10.1007/s00453-015-0066-y">10.1007/s00453-015-0066-y</a> Dvořák, W., Henzinger, M., &#38; Williamson, D. P. (2017). Maximizing a submodular function with viability constraints. <i>Algorithmica</i>. Springer Nature. <a href="https://doi.org/10.1007/s00453-015-0066-y">https://doi.org/10.1007/s00453-015-0066-y</a> 116762022-07-27T14:37:24Z2024-11-06T12:07:55Z