@inproceedings{11792,
  abstract     = {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.},
  author       = {Dvořák, Wolfgang and Henzinger, Monika H and Williamson, David P.},
  booktitle    = {21st Annual European Symposium on Algorithms},
  isbn         = {9783642404498},
  issn         = {1611-3349},
  location     = {Sophia Antipolis, France},
  pages        = {409 -- 420},
  publisher    = {Springer Nature},
  title        = {{Maximizing a submodular function with viability constraints}},
  doi          = {10.1007/978-3-642-40450-4_35},
  volume       = {8125},
  year         = {2013},
}