algorithm - 计算直线最小斯坦纳树的最佳算法是什么？

Question

有许多算法可以找到直线斯坦纳最小树 (RSMT) 的近似值。其中有:

• 一套找到最小生成树的算法
• RST-T(直线单树干斯坦纳树)
• BGA(批量贪心算法)
• BI1S(批量迭代 1-Steiner 树)
• FLUTE(用于 RSMT 构造和线长估算的基于快速查找表的技术)

结果表明，RSMT 的长度可以达到直线生成最小树的 3/2 倍。我没有在其他算法的文献范围内找到。它们存在吗？

FLUTE 似乎是所有算法中最有效的算法，但我不知道它的最坏情况和上限。找到了吗？

有没有任何算法的边界小于 3/2？

Answer 1

Arora和 Mitchell为欧氏斯坦纳树给出了多项式时间近似方案(= 对于所有 epsilon > 0，一个 (1 + epsilon)-近似)。我相信这些想法可以直接适用于直线变体。