多始点1品種1パス多品種流における最小費用流問題の近似アルゴリズム

概要

論文の詳細を見る
本論文では多始点(multi-soruce)1品種1パス多品種流(unsplittable flow)における最小費用流問題を考え, その近似アルゴリズムを提案する.1品種1パス多品種流は高バンド幅ネットワークの接続要求問題やVLSI配線問題の基礎的なモデルになるうるため, 辺素パス問題および多品種流問題の拡張として近年研究されている.一方, 最小費用流問題は古典的ネットワークフロー問題の基礎であるにもかかわらず, 1品種1パス多品種流の最小費用流問題はほとんど研究されていない.本論文では, 多始点1品種1パス多品種流における最小費用流問題の近似アルゴリズムを提案する.手法としては, Kolliopoulos, Steinが1997年および1999年に提案した1始点問題の近似アルゴリズムを多始点の場合に拡張している.とくに, 1999年の過密度3近似のアルゴリズムを拡張して始点数がc個のとき過密度c+4, 費用4近似を達成するアルゴリズムを構築することができた.
一般社団法人情報処理学会の論文
2000-01-17