什麼是計算直線最小斯坦納樹的最佳算法？

Question

有許多算法可以找到直線Steiner最小樹（RSMT）的近似值。其中有：

• 的算法套件，找到最小生成樹
• RST-T（直線單幹Steiner樹）
• BGA（batcheed貪心算法）
• BI1S（成批的迭代1- Steiner樹）
爲RSMT建設和線長估計）
• FLUTE（快速基於查找表的技術

它表明長度的RSMT可以是直線跨越最小樹的3/2倍。我沒有在文獻中找到其他算法。它們存在嗎？

FLUTE似乎是最有效的算法，但我不知道它是最壞的情況和上限。找到了嗎？

是否有任何算法綁定少於3/2？

Answer 1

Arora和Mitchell給出歐幾里德斯坦納樹的多項式時間近似方案（對所有ε> 0，a（1 +ε）近似）。我相信這些想法可以直接適用於直線變體。