自動ニュース作成G
鉄道・道路・電力などあらゆる種類のネットワークについて最小のコストで最大のトランスポートフローを最高速で計算できるアルゴリズムが爆誕 - GIGAZINE
https://gigazine.net/news/20240714-fastest-flow-algorithm/
2024-07-28 22:25:08
タイトルからひょっとしてNPコンプリート
◇
の問題が解けちゃったのかと思ったら
＞ランダウの記号で表すとネットワークのサイズをmとして2000年代まではO(m^1.5)の計算量が必要だったのが、2004年にO(m^1.33)になり、キン氏のアルゴリズムではネットワークのサイズが大きくなるにつれてO(m)に漸近します。
最初からNPコンプリートじゃ無かった
・組み合わせ爆発の話？