Maximizing a Submodular Function with Viability Constraints
详细信息 查看全文
- 作者：Wolfgang Dvořák ; Monika Henzinger ; David P. Williamson
- 关键词：Approximation algorithms ; Submodular functions ; Phylogenetic diversity ; Viability constraints
- 刊名：Algorithmica
- 出版年：2017
- 出版时间：January 2017
- 年：2017
- 卷：77
- 期：1
- 页码：152-172
- 全文大小：
- 刊物类别：Computer Science
- 刊物主题：Algorithm Analysis and Problem Complexity; Theory of Computation; Mathematics of Computing; Algorithms; Computer Systems Organization and Communication Networks; Data Structures, Cryptology and Inform
- 出版者：Springer US
- ISSN：1432-0541
- 卷排序：77
文摘
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 \(\mathsf{NP}\)-hard, we investigate approximation algorithms. We present the first constant factor approximation algorithm if the depth is constant. Its approximation ratio is \((1-\frac{1}{\sqrt{e}})\). 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+\epsilon )\)-approximation algorithm for our problem setting (even for additive functions) and that there is no approximation algorithm for a slight extension of this setting.