algorithm - 寻找斯坦纳森林的近似算法

Question

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

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

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

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

足够的理论。很难找到这样一个权重最小的森林(NP 完全)。你知道有什么更快的近似算法来找到这样一个非最优权重的森林吗？

Answer 1

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

(这是一个 factor-2 算法，但在实践中它可能表现得很好)

Approximation Algorithms

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