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 algorithm. We present the first constant factor approximation algorithm if the depth is constant. Its approximation ratio is (1 - 1/e~(1/2)). 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.
展开▼
机译：我们研究了具有生存力约束的单调子模函数最大化的问题。这个问题源于计算生物学，在计算生物学中，我们得到了一组物种的系统发育树，以及一个有向图，即所谓的食物网，可对这些物种之间的生存能力进行编码。这些食物网通常具有恒定的深度。目的是选择满足生存力要求并具有最大系统发育多样性的k种物种的子集。由于已知此问题是NP难的，因此我们研究了近似算法。如果深度是恒定的，我们提出第一个恒定因子近似算法。它的近似比是（1-1 / e〜（1/2））。该算法不仅适用于具有生存能力约束的系统树，而且适用于具有生存能力约束的任意单调子模块集函数。其次，我们证明，对于我们的问题设置（甚至对于加法函数），没有（1-1 / e +∈）近似算法，并且对于此设置的轻微扩展也没有近似算法。
展开▼
