尋找斯坦納森林的近似算法

考慮加權圖G =（V，E，w）。我們給定了一系列頂點V_i的子集。尋找斯坦納森林的近似算法

斯坦納森林是一個森林，對於頂點的每個子集V_i都將該子集中的所有頂點與樹連接起來。

示例：只有一個子集V_1 = V.在這種情況下，斯坦納森林是整個圖的生成樹。示例：圖P4（具有4個頂點的路徑）和兩個子集：V_1 = {v1，v4}和V_2 = {v2，v3}。這個例子的斯坦納樹就是整個圖。

足夠的理論。以最小的重量找到這樣的森林是很困難的（NP-complete）。你知道有什麼更快的近似算法來找到這樣一個非最佳體重的森林嗎？

這可能適用於SO，但考慮到數學的明顯難度級別，你可能在http://mathoverflow.net上有更好的運氣。 – 2010-04-19 16:42:23

爲了完整性：我在mo.net上提出的同一個問題：http://mathoverflow.net/questions/21859/an-approximate-algorithm-for-finding-steiner-forest-in-a-graph – 2011-05-12 11:55:28

Vijay Vazirani近似算法的第20章描述了一個生成斯坦納森林的模式。該分析採用LP-兩重性，這是他用來確定算法的因素：

（這是一個因素-2算法，但在實踐中可能的票價相當不錯）

另外：請參閱22.5中的說明，其中描述了三篇需要進一步閱讀的論文，包括對該主題的調查。

2010-04-20 18:04:26 cjb

也許你可以重申這個問題作爲其他NP完整，你知道任何次優算法？雖然這只是一個猜測 - 我無法找到這樣的映射與我非常有限的數學技能:)

2010-04-20 14:25:26

回答