直線シュタイナー最小木 (RSMT) の近似を求めるアルゴリズムは多数あります。その中には次のものがあります。
- 最小全域木を見つける一連のアルゴリズム
- RST-T（直線単幹シュタイナー木）
- BGA (一括貪欲アルゴリズム)
- BI1S (バッチ反復 1-Steiner ツリー)
- FLUTE (RSMT 構築およびワイヤ長推定のための高速ルックアップ テーブル ベースの手法)
RSMT の長さは、rectlinear spanning 最小ツリーの 3/2 倍にもなり得ることが示されました。他のアルゴリズムの限界を文献で見つけられませんでした。それらは存在しますか？
FLUTE は最も効率的なアルゴリズムのようですが、それが最悪のケースで上限があるかどうかはわかりません。見つかりましたか？
3/2 未満に制限されたアルゴリズムはありますか?