algorithm - 有向图约束最大生成子树的逼近算法

Question

给定一个有向图，其中每个向量都有非负成本，每个顶点都有非负利润，你如何找到图的最大利润生成子树？我想将成本限制在给定预算内。我正在寻找具有多项式时间复杂度和理论近似因子的问题的近似算法。

Answer 1

a spanning sub-tree

我假设您指的是 arborescence .修复一个根 u(或者尝试所有顶点以获得额外的因子 |V|)。对于每个弧 a，令 x_a 是一个 0-1 指示变量，用于表示树状结构中的成员资格。对于每个顶点 v，让 y_v 相同。显而易见的整数规划是

maximize ∑_v profit(v) y_v
∑_a cost(a) x_a ≤ budget
∀v≠u. ∀S⊆V, u∈S, v∉S. y_v ≤ ∑_{a∈S×(V∖S)} x_a
∀a. x_a ∈ {0, 1}
∀v. y_v ∈ {0, 1}

不幸的是，完整性差距是无限大的。在用其他几个公式遇到同样的问题后，我开始强烈怀疑不存在具有“合理”近似比的近似算法。这个问题有点结合了批量购买机制和预算最大覆盖问题，使得额外覆盖的边际成本变得非常便宜成为可能，这似乎应该导致排除近似的阈值行为.一种出路可能是满足于双标准近似(即，为近似算法提供更大的预算)。