---
_id: '11676'
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 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.
acknowledgement: "The research leading to these results has received funding from
  the European Research\r\nCouncil under the European Union’s Seventh Framework Programme
  (FP/2007-2013)/ERC Grant Agreement No. 340506."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Wolfgang
  full_name: Dvořák, Wolfgang
  last_name: Dvořák
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: David P.
  full_name: Williamson, David P.
  last_name: Williamson
citation:
  ama: Dvořák W, Henzinger MH, Williamson DP. Maximizing a submodular function with
    viability constraints. <i>Algorithmica</i>. 2017;77(1):152-172. doi:<a href="https://doi.org/10.1007/s00453-015-0066-y">10.1007/s00453-015-0066-y</a>
  apa: Dvořák, W., Henzinger, M. H., &#38; Williamson, D. P. (2017). Maximizing a
    submodular function with viability constraints. <i>Algorithmica</i>. Springer
    Nature. <a href="https://doi.org/10.1007/s00453-015-0066-y">https://doi.org/10.1007/s00453-015-0066-y</a>
  chicago: Dvořák, Wolfgang, Monika H Henzinger, and David P. Williamson. “Maximizing
    a Submodular Function with Viability Constraints.” <i>Algorithmica</i>. Springer
    Nature, 2017. <a href="https://doi.org/10.1007/s00453-015-0066-y">https://doi.org/10.1007/s00453-015-0066-y</a>.
  ieee: W. Dvořák, M. H. Henzinger, and D. P. Williamson, “Maximizing a submodular
    function with viability constraints,” <i>Algorithmica</i>, vol. 77, no. 1. Springer
    Nature, pp. 152–172, 2017.
  ista: Dvořák W, Henzinger MH, Williamson DP. 2017. Maximizing a submodular function
    with viability constraints. Algorithmica. 77(1), 152–172.
  mla: Dvořák, Wolfgang, et al. “Maximizing a Submodular Function with Viability Constraints.”
    <i>Algorithmica</i>, vol. 77, no. 1, Springer Nature, 2017, pp. 152–72, doi:<a
    href="https://doi.org/10.1007/s00453-015-0066-y">10.1007/s00453-015-0066-y</a>.
  short: W. Dvořák, M.H. Henzinger, D.P. Williamson, Algorithmica 77 (2017) 152–172.
date_created: 2022-07-27T14:37:24Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2022-09-12T08:58:16Z
day: '01'
doi: 10.1007/s00453-015-0066-y
extern: '1'
external_id:
  arxiv:
  - '1611.05753'
intvolume: '        77'
issue: '1'
keyword:
- Approximation algorithms
- Submodular functions
- Phylogenetic diversity
- Viability constraints
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1611.05753
month: '01'
oa: 1
oa_version: Preprint
page: 152-172
publication: Algorithmica
publication_identifier:
  eissn:
  - 1432-0541
  issn:
  - 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Maximizing a submodular function with viability constraints
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 77
year: '2017'
...