Maximizing a Submodular Function with Viability Constraints

Wolfgang Dvořák (Korresp. Autor*in), Monika Henzinger, David P. Williamson

Veröffentlichungen: Beitrag in FachzeitschriftArtikelPeer Reviewed

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
OriginalspracheEnglisch
Seiten (von - bis)152–172
Seitenumfang21
FachzeitschriftAlgorithmica: an international journal in computer science
Jahrgang77
Ausgabenummer1
Frühes Online-Datum1 Sep. 2015
DOIs
PublikationsstatusVeröffentlicht - Jan. 2017

ÖFOS 2012

  • 102031 Theoretische Informatik

Zitationsweisen