[{"abstract":[{"text":"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.","lang":"eng"}],"intvolume":"        77","publication_status":"published","publication_identifier":{"issn":["0178-4617"],"eissn":["1432-0541"]},"day":"01","scopus_import":"1","author":[{"first_name":"Wolfgang","last_name":"Dvořák","full_name":"Dvořák, Wolfgang"},{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530","first_name":"Monika H"},{"first_name":"David P.","full_name":"Williamson, David P.","last_name":"Williamson"}],"oa_version":"Preprint","title":"Maximizing a submodular function with viability constraints","volume":77,"date_created":"2022-07-27T14:37:24Z","article_type":"original","oa":1,"language":[{"iso":"eng"}],"citation":{"ama":"Dvořák W, Henzinger MH, 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>","ieee":"W. Dvořák, M. H. 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.","short":"W. Dvořák, M.H. Henzinger, D.P. Williamson, Algorithmica 77 (2017) 152–172.","ista":"Dvořák W, Henzinger MH, Williamson DP. 2017. Maximizing a submodular function with viability constraints. Algorithmica. 77(1), 152–172.","chicago":"Dvořák, Wolfgang, Monika H 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>.","apa":"Dvořák, W., Henzinger, M. H., &#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>","mla":"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>."},"issue":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","arxiv":1,"month":"01","page":"152-172","main_file_link":[{"url":"https://arxiv.org/abs/1611.05753","open_access":"1"}],"quality_controlled":"1","article_processing_charge":"No","doi":"10.1007/s00453-015-0066-y","publisher":"Springer Nature","_id":"11676","date_updated":"2022-09-12T08:58:16Z","type":"journal_article","extern":"1","publication":"Algorithmica","status":"public","date_published":"2017-01-01T00:00:00Z","acknowledgement":"The research leading to these results has received funding from the European Research\r\nCouncil under the European Union’s Seventh Framework Programme (FP/2007-2013)/ERC Grant Agreement No. 340506.","year":"2017","external_id":{"arxiv":["1611.05753"]},"keyword":["Approximation algorithms","Submodular functions","Phylogenetic diversity","Viability constraints"]}]