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