计算直线最小斯坦纳树的最佳算法是什么？
有许多算法可以找到直线 Steiner 最小树 (RSMT) 的近似值。其中包括：
- 一套寻找最小生成树的算法
- RST-T（直线单主干 Steiner 树）
- BGA（批量贪婪算法）
- BI1S（批量迭代 1-Steiner 树）
- FLUTE（基于快速查找表的 RSMT 构造和线长技术）估计）
表明RSMT的长度可以达到直线生成最小树长度的3/2。我在文献中没有找到其他算法的范围。它们存在吗？
FLUTE 似乎是最有效的算法，但我不知道它的最坏情况和上限。被发现了吗？
有没有任何算法的界限小于 3/2？
There are many algorithms that find approximations of rectilinear Steiner minimum trees (RSMT). Among them are:
- a suite of algorithms that find minimum spanning trees
- RST-T (rectilinear single trunk Steiner tree)
- BGA (batcheed greedy algorithm)
- BI1S (Batched Iterated 1-Steiner tree)
- FLUTE (Fast Lookup Table Based Technique for RSMT Construction and Wirelength Estimation)
It was showed that length of RSMT can be as much as 3/2 times that of rectlinear spanning minimum tree. I didn't find in literature bounds for other algorithms. Do they exist?
FLUTE seems to be the most efficient algorithm from all but I don't know it's worst case and upper bound. Was it found?
Does any algorithm have bound less than 3/2?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
阿罗拉 和 Mitchell 给出了多项式时间近似方案（= 对于所有 epsilon > 0，欧几里得施泰纳树的 (1 + epsilon)-近似值。我相信这些想法可以直接适应直线变体。
Arora and Mitchell gave polynomial-time approximation schemes (= for all epsilon > 0, a (1 + epsilon)-approximation) for Euclidean Steiner tree. I believe the ideas can be adapted straightforwardly to the rectilinear variant.