algorithm - 寻找施泰纳森林的近似算法

Question

考虑一个加权图 G=(V,E,w)。我们得到一组顶点 V_i 的子集。

斯坦纳森林是一个森林，对于每个顶点子集 V_i 将这个子集中的所有顶点与一棵树连接起来。

示例：只有一个子集 V_1 = V。在这种情况下，Steiner 森林是整个图的生成树。

示例：图 P4（具有 4 个顶点的路径）和两个子集：V_1 = {v1, v4} 和 V_2 = {v2, v3}。此示例的 Steiner 树是整个图。

理论够了。很难找到这样一个重量最小的森林（NP-complete）。你知道任何更快的近似算法来找到这样一个非最优权重的森林吗？

score 4 · Accepted Answer

Vijay Vazirani 在 Approximation Algorithms 的第 20 章描述了生成 Steiner Forest 的模式。分析使用 LP 对偶，他用它来确定算法的因子：

（这是一个因子 2 算法，但实际上它可能运行得很好）

另外：请参阅 22.5 中的注释，其中描述了三篇论文以供进一步阅读，包括对该主题的调查。

score 0 · Accepted Answer

也许您可以将此问题重述为其他 NP 完全问题，您知道任何次优算法？不过，这只是一个猜测——我无法用我非常有限的数学技能找到这样的映射:)

2 回答 2