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

Question

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

algorithmgraph-theorytreeapproximation

3

考虑一个带权图 G=(V,E,w)。我们有一个顶点子集 V_i 的家族。

Steiner 森林是一个森林，对于每个顶点子集 V_i，它连接此子集中的所有顶点以形成一棵树。

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

例如：一个含有4个顶点的路径图 P4 和两个子集：V_1={v1、v4}和 V_2={v2、v3}。此例的 Steiner 树是整个图。

以上是理论知识。寻找最小权重的 Steiner 森林是困难的（NP 完全问题）。您是否了解任何更快的近似算法来寻找具有非最优权重的这样一棵树？

- Tadeusz A. Kadłubowski

1

这个问题可能适合在SO上提问，但考虑到数学的难度水平，你在http://mathoverflow.net上可能会有更好的运气。 - Michael Petrotta

为了完整起见：我在mo.net上提出了同样的问题：http://mathoverflow.net/questions/21859/an-approximate-algorithm-for-finding-steiner-forest-in-a-graph - Tadeusz A. Kadłubowski

2个回答

0

也许你可以将这个问题转化为其他 NP 完全问题，然后使用你所知道的任何次优算法来解决它？不过这只是一个猜测，因为我的数学技能非常有限，我找不到这样的映射 :)

- Victor Sorokin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- cjb · Accepted Answer

《近似算法》一书第20章描述了一种生成斯坦纳森林的方案。分析使用LP对偶性，用于确定算法因子：（这是一个2倍近似算法，但在实践中它可能表现得非常好）。另外，在22.5中请注意描述三篇论文以供进一步阅读，其中包括该主题的调查。请参考此链接：Approximation Algorithms。