---
res:
  bibo_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 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.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Wolfgang
      foaf_name: Dvořák, Wolfgang
      foaf_surname: Dvořák
  - foaf_Person:
      foaf_givenName: Monika H
      foaf_name: Henzinger, Monika H
      foaf_surname: Henzinger
      foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
    orcid: 0000-0002-5008-6530
  - foaf_Person:
      foaf_givenName: David P.
      foaf_name: Williamson, David P.
      foaf_surname: Williamson
  bibo_doi: 10.1007/s00453-015-0066-y
  bibo_issue: '1'
  bibo_volume: 77
  dct_date: 2017^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/0178-4617
  - http://id.crossref.org/issn/1432-0541
  dct_language: eng
  dct_publisher: Springer Nature@
  dct_subject:
  - Approximation algorithms
  - Submodular functions
  - Phylogenetic diversity
  - Viability constraints
  dct_title: Maximizing a submodular function with viability constraints@
...