組合せ最適化 理論において、サブモジュラフローは、最小費用フロー問題、マトロイド交差、重み付き有向グラフにおける最小重み二重結合の計算問題などを特殊なケースとして含む、最適化問題の一般的なクラスである。これはもともとジャック・エドモンズとリック・ジャイルズによって定式化され[1] 、多項式時間で解くことができる。[2] [3] [4]
古典的な最小コストフロー問題では、入力はフローネットワークであり、各辺あたりのフロー量の下限と上限、および各辺に沿った単位フローあたりのコストを指定する容量が与えられます。目標は、各辺の容量に従い、各頂点への流入量の合計が流出量の合計に等しいというキルヒホッフの法則に従い、総コストが最小となるフロー量のシステムを見つけることです。サブモジュラフローでも、グラフの頂点の集合に対するサブモジュラ集合関数が与えられます。キルヒホッフの法則に従う代わりに、すべての頂点集合について、過剰フロー（集合を流入と流出の差にマッピングする関数）がサブモジュラ関数によって与えられた値以下になることが要件となります。[4]
参考文献
- ^ エドモンズ、ジャック; ジャイルズ、リック (1977)、「グラフ上の劣モジュラ関数の最小最大関係」、整数計画法の研究 (Proc. Workshop, Bonn, 1975)、Annals of Discrete Mathematics、第1巻、北ホランド、アムステルダム、pp. 185– 204、MR 0460169
- ^ Grötschel, M.; Lovász, L.; Schrijver, A. (1981)、「楕円体法と組合せ最適化におけるその帰結」、Combinatorica、1 (2): 169– 197、doi :10.1007/BF02579273、MR 0625550、S2CID 43787103
- ^ Gabow, Harold N. (1993)、「劣モジュラーフロー問題のためのコストスケーリングアルゴリズムのフレームワーク」、第34回コンピュータサイエンスの基礎に関する年次シンポジウム（FOCS）の議事録、米国カリフォルニア州パロアルト、1993年11月3-5日、IEEEコンピュータ協会、pp. 449– 458、doi :10.1109/SFCS.1993.366842、S2CID 32162097
- ^ ab Fleischer, Lisa; Iwata, Satoru (2000), 「劣モジュラ関数の最小化と劣モジュラフローのための改良アルゴリズム」, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing , Association for Computing Machinery, pp. 107– 116, doi : 10.1145/335305.335318 , MR 2114523
