Logo der Universität Wien

Maximizing a Submodular Function with Viability Constraints

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

GrafikTop
Authors
GrafikTop
Citation
Category
Journal Paper
Divisions
Theory and Applications of Algorithms
Subjects
Theoretische Informatik
Journal or Publication Title
Algorithmica: an international journal in computer science
ISSN
0178-4617
Publisher
Springer US
Date
September 2015
Export
GrafikTop
Contact us
Faculty of Computer Science
University of Vienna

Währinger Straße 29
A-1090 Vienna