给定一个有向图，其中每个向量的成本都是非负的，每个顶点的利润都是非负的，你如何找到具有最大利润的图的生成子树？我想将成本限制在给定的预算范围内。我正在寻找多项式时间复杂度问题的近似算法，以及理论近似因子。
问问题
231 次
1 回答
1
生成子树
我将假设您的意思是arborescence。修复一个根 u（或者只是尝试所有顶点以获得额外的 |V| 因子）。对于每条弧a，令x a是一个 0-1 指示变量，用于表示树状结构中的成员资格。对于每个顶点v，让y v相同。明显的整数程序是
最大化 ∑ v利润( v ) y v
∑ a成本( a ) x a ≤ 预算
∀ 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}
不幸的是，完整性差距是无限的。在与其他几个公式有同样的问题之后，我开始相当强烈地怀疑没有具有“合理”近似比的近似算法。这个问题将批量购买机制与预算最大覆盖问题相结合，使得额外覆盖的边际成本变得非常便宜，这似乎应该导致那种排除近似值的阈值行为. 一种出路可能是适应双准则近似（即，给近似算法更大的预算）。
于 2012-03-29T17:16:43.910 回答