[{"volume":8125,"extern":"1","arxiv":1,"doi":"10.1007/978-3-642-40450-4_35","day":"01","abstract":[{"lang":"eng","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."}],"date_updated":"2023-02-21T16:28:24Z","citation":{"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.","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.","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.","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>.","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>"},"year":"2013","external_id":{"arxiv":["1611.05753"]},"publisher":"Springer Nature","page":"409 - 420","quality_controlled":"1","publication_status":"published","date_created":"2022-08-11T11:18:19Z","article_processing_charge":"No","alternative_title":["LNCS"],"title":"Maximizing a submodular function with viability constraints","intvolume":"      8125","_id":"11792","scopus_import":"1","author":[{"last_name":"Dvořák","first_name":"Wolfgang","full_name":"Dvořák, Wolfgang"},{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Williamson","first_name":"David P.","full_name":"Williamson, David P."}],"main_file_link":[{"url":"https://arxiv.org/abs/1611.05753","open_access":"1"}],"related_material":{"record":[{"id":"11792","relation":"later_version","status":"public"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","publication_identifier":{"isbn":["9783642404498"],"issn":["1611-3349"]},"oa":1,"date_published":"2013-09-01T00:00:00Z","type":"conference","conference":{"name":"ESA: European Symposium on Algorithms","start_date":"2013-09-02","location":"Sophia Antipolis, France","end_date":"2013-09-04"},"language":[{"iso":"eng"}],"oa_version":"Preprint","month":"09","publication":"21st Annual European Symposium on Algorithms"}]