容量スケーリング法のすゝめ

要約 最小費用流問題に対する最短路反復法(Successive Shortest Path, SSP)や Primal-Dual 法1と呼ばれるアルゴリズムは, 少し弄ると弱多項式時間アルゴリズムにできる. 具体的には, $O(\U \cdot \mathrm{SP_+}(n, m, nC))$ が $O(m \log \U \cdot \mathrm{SP_+}(n, m, nC))$ になる. $\mathrm{SP_+}(n, m, nC)$ は$n$ 頂点 $m$ 辺, 費用高々 $nC$ のグラフの一点から全点への最短路問題を解くのにかかる時間. 以下では実装をサボったダイクストラ法なので $O(m \log m)$ だが, $\exists k: m = O(n^k)$ を仮定すると合計 $O(m^2 \log \U \log n)$. まえがき ぼくの考えたさいきょうのフロー