点容量型多品種フロー問題に対する双対降下アルゴリズムとその応用

摘要

本論文では，点容量型無向ネットワークの半整数最大マルチフローを求める0（mn~3logk）時間の組合せ的アルゴリズムを与える．ここで，nはネットワークの頂点数，mは枝数，kはターミナルの個数である．これはこの問題に対する最初の組合せ的強多項式時間アルゴリズムである．我々のアルゴリズムは，グラフ構造上の離散凸関数の理論に基いて設計される．このアルゴリズムを用いることで，点マルチウェイかソトに対するGarg-Vazirani-Yannakakisの2近似アルゴリズムが組合せ的かつ強多項式時間で実現できるようになった．