寻找Steiner森林的一种近似算法
寻找Steiner森林的一种近似算法
提问于 2010-04-20 00:38:52
考虑一个加权图G=(V，E，w)。我们得到了一族顶点的子集V_i。
斯坦纳森林是一个森林，对于每个顶点子集，V_i使用树将此子集中的所有顶点连接起来。
例如:只有一个子集V_1 = V。在这种情况下，斯坦纳森林是整个图的生成树。
示例:图P4 (具有4个顶点的路径)和两个子集: V_1 = {v1，v4}和V_2 = {v2，v3}。本例中的Steiner树是整个图。
理论已经够多了。找到这样一个权重最小的森林是困难的(NP-完全)。你知道有什么更快的近似算法来找到这样一个权重不是最优的森林吗？
回答 2
Stack Overflow用户
回答已采纳
发布于 2010-04-21 02:04:26
Vijay Vazirani的近似算法的第20章描述了一个生成Steiner森林的模式。分析使用LP-duality，他使用它来确定算法的因子：
(这是一个因子2算法，但实际上它可能运行得很好)
Approximation Algorithms
另外:请参阅22.5中的注释，其中描述了三篇论文以供进一步阅读，包括对该主题的调查。
Stack Overflow用户
发布于 2010-04-20 22:25:27
也许你可以将这个问题重新表述为其他NP-完全问题，对于这些问题，你知道任何次优算法吗？不过，这只是一个猜测--我有限的数学技能找不到这样的映射:)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2669163
复制相关文章
相似问题
腾讯云开发者
