Maximizing a submodular function with viability constraints Dvořák, Wolfgang Henzinger, Monika H ; https://orcid.org/0000-0002-5008-6530 Williamson, David P. Approximation algorithms Submodular functions Phylogenetic diversity Viability constraints 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 Nature 2017 info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/11676 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> eng info:eu-repo/semantics/altIdentifier/doi/10.1007/s00453-015-0066-y info:eu-repo/semantics/altIdentifier/issn/0178-4617 info:eu-repo/semantics/altIdentifier/e-issn/1432-0541 info:eu-repo/semantics/altIdentifier/arxiv/1611.05753 info:eu-repo/semantics/openAccess