6J-02
シュタイナー森問題に対する近似アルゴリズムの実際的性能評価
○菅原惇平，鮏川矩義，浅野孝夫（中大）
シュタイナー森問題は，辺にコストの付随するネットワークとk組のターミナル点対が与えられたときに，どのターミナル点対も連結であるような部分ネットワークの中で，コスト最小のものを求める問題である．この問題に対して2近似アルゴリズムは知られていたが，いずれもIP定式化のLP緩和に基づくものであった．一方，2015年のACM STOCで，LP緩和によらない貪欲法に基づくアルゴリズムがGupta-Kumarにより提案され，その性能保証が高々96であることが示された．本発表では，これらのアルゴリズムを実装して様々な入力に対する実験を行い，実際的性能の比較・評価を与える．
footer 著作権について 倫理綱領 プライバシーポリシー セキュリティ 情報処理学会