ETHチューリッヒの研究者、最速のフローアルゴリズムを開発
(ethz.ch)- ETH ZurichのRasmus Kyng研究チームは、ネットワーク上で最大フローを見つけ、輸送コストを最小化する問題を、ほぼ数学的限界の速度で計算するアルゴリズムを開発した
- 新アルゴリズムは、ネットワークデータを読み込む時間とほぼ同じ規模で答えを出すほぼ線形時間のアプローチであり、鉄道・道路・水路・インターネットのようなネットワーク計算に適用できる
- 過去には接続数をmとすると、2000年以前はm^1.5、2004年にはm^1.33程度だったが、Kyngのアプローチはデータ読み込み後の追加計算時間を無視できる水準まで下げた
- 研究チームは、静的・有向ネットワークを超え、接続が追加される増分グラフと削除される減少グラフでも、最短経路と最小費用最大フローをほぼ線形時間で計算する
- Gotthard Base Tunnelの閉鎖・部分再開通、A13高速道路の土砂崩れのように、実際のネットワークが変化する状況で最適経路を素早く再計算する基盤となる
ネットワークフロー問題をほぼ限界速度で計算
- Rasmus Kyng研究チームのネットワークフローアルゴリズムは、ネットワーク上で可能な最大フローを見つけながら、輸送コストを最小化する問題を扱う
- CopenhagenからMilanまで、できるだけ多くの物資を最も速く、安く運ぶ経路を探す状況が代表的な例である
- 鉄道、道路、水路、インターネットのように接続と容量を持つネットワークで、最適な低コストのフローを計算できる
- 計算速度は、コンピュータがネットワークデータを読み込む時間とほぼ同じ水準まで短縮された
なぜ「最速」のアルゴリズムなのか
- 以前は、最適フローを計算する時間が、ネットワークデータを処理する時間よりはるかに長かった
- ネットワークが大きく複雑になるほど、必要な計算時間は問題サイズよりも速く増加していた
- Kyngのアプローチは、計算時間とネットワークサイズが同じ比率で増えるようにする
- ネットワークの接続数をmとすると、データを1回読み込むだけでmの時間がかかる
- 2000年以前には、m^1.5より速く計算するアルゴリズムはなかった
- 2004年には、問題を解くのに必要な計算量がm^1.33まで減った
- Kyngのアルゴリズムは、データを読み込んだ後、解に到達するための追加計算時間を無視できる水準まで下げた
ほぼ線形時間アルゴリズムの評価と拡張
- Kyng研究チームは2年前、この概念の数学的証明を含む論文を発表した
- このようにほぼ最適に速いアルゴリズムは、ほぼ線形時間アルゴリズムと呼ばれる
- Daniel A. Spielmanはこのアルゴリズムを、馬車を追い抜くPorscheにたとえた
- 同論文は2022年のIEEE Annual Symposium on Foundations of Computer Science、FOCSでBest Paper Awardを受賞した
- Communications of the ACMもこの研究を取り上げ、Quanta編集部はKyngのアルゴリズムを2022年のコンピュータサイエンスにおける10大発見の1つに選んだ
静的ネットワークから変化するネットワークへ
- 初期のアルゴリズムは、接続方向が決まっている固定・静的ネットワークに焦点を当てていた
- 有向接続は、都市の道路網における一方通行のような構造である
- その後、研究チームは時間とともに段階的に変化するネットワークでも最適フローを計算するアルゴリズムを開発した
- Simon MeierhansはVancouverで開催されたAnnual ACM Symposium on Theory of Computing、STOCで、新しいほぼ線形時間アルゴリズムを発表した
- このアルゴリズムは、新しい接続が追加されるネットワークの最小費用最大フロー問題を解く
- 10月のIEEE Symposium on Foundations of Computer Science、FOCSに採択された2本目の論文では、接続の削除も処理するアルゴリズムを開発した
- 2つのアルゴリズムは、接続が追加または削除されるネットワークで最短経路を特定する
実際のネットワーク変化の例
- SwitzerlandのGotthard Base Tunnelは2023年夏以降、完全閉鎖された後に部分再開通した
- Gotthard Road Tunnelの主要な代替ルートであるA13高速道路の一部は、最近の土砂崩れで破壊された
- こうした変化が起きると、コンピュータ、オンライン地図サービス、経路計画ツールは、MilanとCopenhagenの間の最小コスト・最短の接続を再計算する必要がある
- Kyngの新アルゴリズムは、接続の追加や削除があるネットワークでも、ほぼ線形時間で最適経路を計算する
- 迂回路や新しい経路ができて接続が追加される場合でも、追加計算時間は無視できる水準である
既存の2つの戦略と新しい組み合わせ方
- ネットワークフロー計算では、最適フローと最小コスト経路を見つけるために、ネットワークを何度も解析する必要がある
- 各反復では、どの接続が開いているか、閉じているか、容量上限に達して混雑しているかといった変化を検討する
- Kyng以前のコンピュータ科学者は、主に2つの戦略のうち1つを使っていた
- 鉄道網モデル: 各反復で、トラフィックフローが変化したネットワークの一区間全体を計算する
- 電力網モデル: 各反復でネットワーク全体を計算するが、各区間の変化したフローに統計的平均値を使って計算を高速化する
- Kyng研究チームは2つの戦略の利点をまとめ、新しい組み合わせアプローチを作った
- Maximilian Probst Gutenbergは、小さく効率的で低コストな計算ステップを多数組み合わせれば、少数の大きなステップよりはるかに速いと見ている
フローアルゴリズムの歴史的文脈
- ネットワークフロー問題は、1950年代にアルゴリズムで体系的に解かれた初期の問題の1つだった
- フローアルゴリズムは、理論計算機科学が独立した研究分野として確立するうえで重要な役割を果たした
- Lester R. Ford Jr.とDelbert R. Fulkersonのよく知られたアルゴリズムも、この時期に生まれた
- Ford-Fulkersonアルゴリズムは、各経路の容量を超えない範囲で、できるだけ多くの物資をネットワークで輸送する最大フロー問題を効率的に解く
- その後の研究により、最大フロー問題、最小費用問題、複数のネットワークフロー問題が、一般的な最小費用フロー問題の特殊ケースであることが示された
以前のアルゴリズムの限界と2004年の転換
- Kyngの研究以前の多くのアルゴリズムは、特定の問題を効率的に解くことはできたが、十分に速くなく、より広い最小費用フロー問題へ拡張するのが難しかった
- 1970年代の先駆的なフローアルゴリズムを作ったJohn Edward Hopcroft、Richard Manning Karp、Robert Endre Tarjanは、それぞれTuring Awardを受賞した
- Karpは1985年に受賞した
- HopcroftとTarjanは1986年に受賞した
- 2004年にDaniel Spielman、Shang-Hua Teng、その後Samuel Daitchは、最小費用フロー問題にも高速で効率的な解法を提供するアルゴリズムを作成した
- このグループは視点を鉄道から電力網の電力フローへ移した
- 電力網では、電流の流れを、すでに別の電流が流れている接続へ部分的に迂回させることができる
- KyngはSpielmanのネットワーク全体向けの強力なアルゴリズム的アプローチをそのまま踏襲せず、部分経路計算のアイデアをHopcroftとKarpの以前のアプローチに適用した
- 各反復で部分経路を計算したことが、全体のフロー計算を高速化するうえで大きな役割を果たした
新しい数学ツールとデータ構造
- ETH Zurich研究チームの進展は、新アルゴリズムだけでなく、計算をさらに高速化する数学ツールの設計にも基づいている
- 研究チームは、ネットワークデータを整理する新しいデータ構造を開発した
- このデータ構造により、ネットワーク接続の変化を非常に速く特定できる
- 変化を素早く特定できることは、アルゴリズムによる解法の速度を高める要素として機能する
- ほぼ線形時間アルゴリズムと新しいデータ構造は、以前は効率的に計算できなかった非常に大きな問題を解くための基盤を整える
関連論文と資料
- Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality: 減少グラフにおける最小費用フローなどを扱うFOCS 2024論文
- Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow: 増分グラフにおけるサイクル検出、SCC、s-t最短経路、最小費用フローを扱うSTOC 2024論文
- Maximum Flow and Minimum-Cost Flow in Almost-Linear Time: 最大フローと最小費用フローをほぼ線形時間で解くFOCS 2022論文
- Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow: Communications of the ACMの関連記事
- Researchers Achieve ‘Absurdly Fast’ Algorithm for Network Flow: Quanta Magazineの2022年の関連記事
1件のコメント
Hacker Newsのコメント
このアルゴリズムは n -> inf の極限で漸近的にほぼ線形である。
動画の最後では、このアルゴリズムのどんな実装も現実世界では既存のアルゴリズムに勝つのは難しいと述べている。
https://cacm.acm.org/research/almost-linear-time-algorithms-...
https://en.wikipedia.org/wiki/Galactic_algorithm
可能な最速という表現は、本当に大胆な主張だ。
時間を1%しか使わずに99%の品質を出すほうが、ずっと実用的なことが多い。
興味深いことに、同じ人物が理論専用アルゴリズムを実際によく動くようにする研究もしている [1]。
ただしその過程にはまた20年ほどかかるようだ。[1] は2004年の理論的ブレークスルー [2] の上に積み上げられたもので、私の理解では、こうしたアルゴリズムが2024年になってようやく実運用で動き始めた。だとすると、実用的な最小費用フローアルゴリズムは2044年ごろに期待できるかもしれない。
[1] https://arxiv.org/pdf/2303.00709
[2] https://arxiv.org/abs/cs/0310051
それでも理論的には素晴らしい結果だ。
複雑性を指標にすることに、完全に道を見失ったように感じることがある。
複雑性指標を狂ったレベルまで最適化したが、実際には役に立たないアルゴリズムがますます増えている。
簡単な成果がすべて取り尽くされたあと、アルゴリズム研究はまた一つの高度に専門化された分野になり、ごく近い分野の研究者でもなければ、大半の論文は時間をかける価値があまりない。
関連記事: https://news.ycombinator.com/item?id=31149038 (コメント40件)
https://news.ycombinator.com/item?id=31675015 (コメント72件)
論文やコードはどこにある？
https://cacm.acm.org/research/almost-linear-time-algorithms-...
ここで混乱する点がある。o(n) は O(n) より強い命題のように見える。
すべての o(n) アルゴリズムは O(n) だが、その逆は成り立たないからだ。さらに、o(n) はどんなに小さな n にも適用され、O(n) は n -> inf のときにしか適用されないなら、このアルゴリズムは小さな n にも適用できるはずではないか？ だとすると、上で言われている銀河アルゴリズムの反対であるべきではないか？ 何か見落としているのだろうか？
f(n) = o(g(n)) の定義は、おおよそ lim (n -> infinity) f(n)/g(n) = 0 である。言い換えると、十分大きな n については g が f より速く成長するという意味だ。
例えば f(n) = 10n if n < 1000 else 1e1000 のような関数は o(n) である。n が大きくなると 1e1000/n が 0 に向かうからだ。これは、n = 1000 までは 101000 まで指数的に増加し、その後は定数のままである区分的関数の疑似 Python 表現だ。
記憶が正しければ、3↑↑64 は Graham 数だ。
くそったれな定数係数め、空に向かって拳を振り上げたくなる。
要約には時間が m^(1+o(1)) としか書かれていない。
もっと具体的な上界がどこかに書かれているか知っている人はいる？
https://de.m.wikipedia.org/wiki/Landau-Symbole
別の言い方をすると、任意の ɛ>1 に対して時間 O(m^ɛ) で実行されるアルゴリズム図式が得られる。
little-o は n が無限大に向かうとき 0 に近づく関数で、漸近的に無視可能と呼ばれる。