[{"arxiv":1,"article_processing_charge":"No","_id":"11792","date_published":"2013-09-01T00:00:00Z","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 algorithm. We present the first constant factor approximation algorithm if the depth is constant. Its approximation ratio is (1−1𝑒√). 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"}],"publication_status":"published","main_file_link":[{"url":"https://arxiv.org/abs/1611.05753","open_access":"1"}],"oa":1,"volume":8125,"oa_version":"Preprint","year":"2013","external_id":{"arxiv":["1611.05753"]},"scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-02-21T16:28:24Z","publication_identifier":{"isbn":["9783642404498"],"issn":["1611-3349"]},"page":"409 - 420","month":"09","extern":"1","date_created":"2022-08-11T11:18:19Z","publisher":"Springer Nature","publication":"21st Annual European Symposium on Algorithms","quality_controlled":"1","intvolume":"      8125","status":"public","citation":{"ieee":"W. Dvořák, M. H. Henzinger, and D. P. Williamson, “Maximizing a submodular function with viability constraints,” in <i>21st Annual European Symposium on Algorithms</i>, Sophia Antipolis, France, 2013, vol. 8125, pp. 409–420.","ista":"Dvořák W, Henzinger MH, Williamson DP. 2013. Maximizing a submodular function with viability constraints. 21st Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LNCS, vol. 8125, 409–420.","chicago":"Dvořák, Wolfgang, Monika H Henzinger, and David P. Williamson. “Maximizing a Submodular Function with Viability Constraints.” In <i>21st Annual European Symposium on Algorithms</i>, 8125:409–20. Springer Nature, 2013. <a href=\"https://doi.org/10.1007/978-3-642-40450-4_35\">https://doi.org/10.1007/978-3-642-40450-4_35</a>.","mla":"Dvořák, Wolfgang, et al. “Maximizing a Submodular Function with Viability Constraints.” <i>21st Annual European Symposium on Algorithms</i>, vol. 8125, Springer Nature, 2013, pp. 409–20, doi:<a href=\"https://doi.org/10.1007/978-3-642-40450-4_35\">10.1007/978-3-642-40450-4_35</a>.","short":"W. Dvořák, M.H. Henzinger, D.P. Williamson, in:, 21st Annual European Symposium on Algorithms, Springer Nature, 2013, pp. 409–420.","apa":"Dvořák, W., Henzinger, M. H., &#38; Williamson, D. P. (2013). Maximizing a submodular function with viability constraints. In <i>21st Annual European Symposium on Algorithms</i> (Vol. 8125, pp. 409–420). Sophia Antipolis, France: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-642-40450-4_35\">https://doi.org/10.1007/978-3-642-40450-4_35</a>","ama":"Dvořák W, Henzinger MH, Williamson DP. Maximizing a submodular function with viability constraints. In: <i>21st Annual European Symposium on Algorithms</i>. Vol 8125. Springer Nature; 2013:409-420. doi:<a href=\"https://doi.org/10.1007/978-3-642-40450-4_35\">10.1007/978-3-642-40450-4_35</a>"},"title":"Maximizing a submodular function with viability constraints","conference":{"location":"Sophia Antipolis, France","start_date":"2013-09-02","end_date":"2013-09-04","name":"ESA: European Symposium on Algorithms"},"day":"01","author":[{"last_name":"Dvořák","first_name":"Wolfgang","full_name":"Dvořák, Wolfgang"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H"},{"full_name":"Williamson, David P.","first_name":"David P.","last_name":"Williamson"}],"type":"conference","alternative_title":["LNCS"],"related_material":{"record":[{"relation":"later_version","id":"11792","status":"public"}]},"language":[{"iso":"eng"}],"doi":"10.1007/978-3-642-40450-4_35"}]