組合せ最適化特論

組合せ最適化特論第 1 回（多面体的組合せ論）担当: 相馬輔 2026/04/23 1 /
30

本講義の概要組合せ最適化の定跡とアルゴリズムを学ぶ． • 二部マッチング，最大流，マトロイドなどの定番問題 • 最大最小定理 • 線形計画法・多面体を用いたアルゴリズム設計 • 劣モジュラ最適化としての統一的視点
事務連絡 • スライドと録画は毎回 google drive にアップロードします • Oﬃce hour (随時) 2 / 30

劣モジュラ最小化ネットワークフロー最小費用流マトロイド交差最大流重みつき二部マッチング重みなし二部マッチング二部マッチング
マトロイドマトロイド 3 / 30

各回の内容（予定） I 1 (4/23) イントロ+多面体的組合せ論（線形計画法の復習，整数多面体，完全単模行列） (4/30) 休み 2 3
4 5 (5/7) 二部マッチング①（Konig-Egervary の定理，増加道アルゴリズム，ハンガリー法） (5/14) 二部マッチング②（最短路問題の復習，逐次最短路法と主双対法，最適性基準からの見方） (5/21) 最大流① （定式化，最大流最小カット定理，応用例） (5/28) 最大流②（残余ネットワーク，Ford–Fulkerson 法，Edmonds–Karp のアルゴリズム） 4 / 30

各回の内容（予定） II (6/4) 休み 6 (6/11) 最小費用流①（定式化，輸送問題，最大流との関係） (6/18) 休み (6/25)
休み 7 (7/2) 最小費用流②（逐次最短路法，容量スケーリング法） 8 (7/9) マトロイド（定義と公理系，貪欲法，マトロイド多面体） 9 (7/16) 独立マッチング・マトロイド交差（定義，応用例，Edmonds の最大最小定理，増加道アルゴリズム） (7/23) 休み 5 / 30

各回の内容（予定） III 10 (7/30) 劣モジュラ関数①（諸例，劣モジュラ基多面体，Lovász 拡張，劣モジュラ最小化） 11 (8/6) 劣モジュラ関数②（劣モジュラ最大化，近似アルゴリズム，貪欲法）
12 (どこか) 精選トピック① 13 (どこか) 精選トピック② • レポート課題を 6 月と期末に出す予定 • 精選トピックの日時は今後調整 6 / 30

参考図書本講義のレベル • 垣村『組合せ最適化への招待モデルとアルゴリズム』 SGC ライブラリ, 2024. . .
. . . . . . . . . . . . . . . . . . . . . . . . 色々なトピックがコンパクトにまとまっていて手軽大学院生〜研究者向け • Korte and Vygen, Combinatorial Optimization: Theory and Algorithms, 6th ed, Springer, 2018. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Springer Link から DL 可能 • 『組合せ最適化原書 6 版: 理論とアルゴリズム』, 丸善出版, 2022. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 上の和訳 • Schrijver, Combinatorial Optimization: Polyhedra and Eﬃciency, Springer, 2003. . . . . . . . . . . . . . . . . . . . . . . . . . . 凄い文量だがトピックごとに読める．大百科として 7 / 30

目次 1. 組合せ最適化とは・組合せ最適化とは？・組合せ最適化問題を「解く」とは？・多項式時間とは？ 2.
線形計画の復習・主問題・双対問題・相補性条件・多面体 3. 整数多面体，完全単模行列・完全単模行列・整数多面体・整数多面体と LP の整数性 8 / 30

組合せ最適化とは離散的な対象の中から最も良いものを効率的に求める方法論 X1 X2 .. . Y Xn ネットワークマッチング
機械学習・統計 10 / 30

例: 割当問題割当問題入力コスト cij ∈ R (1 ≤
i, j ≤ n) 出力総コスト最小のマッチング i 輸送コスト cij j マッチング... どの頂点にも 1 本だけ枝が接続しているような枝部分集合 11 / 30

例: 割当問題割当問題入力コスト cij ∈ R (1 ≤
i, j ≤ n) 出力総コスト最小のマッチング i 輸送コスト cij j マッチング... どの頂点にも 1 本だけ枝が接続しているような枝部分集合総コスト = c11 + c23 + c32 . 11 / 30

例: 巡回セールスマン問題巡回セールスマン問題入力枝コスト cij ∈ R (1 ≤
i, j ≤ n) 出力各頂点を一度だけ通る閉路で総コスト最小のもの i 枝コスト ci j j 12 / 30

例: 最大被覆問題最大被覆問題入力 V : 基地局候補地の集合, k ∈ Z+
出力 S ⊆ V で |S| ≤ k かつ S に設置したときの被覆範囲が最大となるもの 13 / 30

愚直な方法: 全探索解をすべて調べて，その中から最適解を選ぶ！ 14 / 30

愚直な方法: 全探索解をすべて調べて，その中から最適解を選ぶ！巡回セールスマン問題の場合 1 秒間に 10 京 (= 1017
) 通り調べられるとする．頂点数 n 計算時間 ≈ n! 10 3.6 × 10−11 秒 20 24 秒 30 3168 万年 14 / 30

) 通り調べられるとする．頂点数 n 計算時間 ≈ n! 10 3.6 × 10−11 秒 20 24 秒 30 3168 万年引用: 『フカシギの数え方』おねえさんといっしょ！みんなで数えてみよう！ https://www.youtube.com/watch?v=Q4gTV4r0zRs 14 / 30

) 通り調べられるとする．頂点数 n 計算時間 ≈ n! 10 3.6 × 10−11 秒 20 24 秒 30 3168 万年引用: 『フカシギの数え方』おねえさんといっしょ！みんなで数えてみよう！ https://www.youtube.com/watch?v=Q4gTV4r0zRs 現実的ではないので，より効率的なアルゴリズムを研究する必要！効率的って何だろう？ 14 / 30

アルゴリズムの時間計算量アルゴリズムの時間計算量入力の大きさ n に対して，アルゴリズムが最大で何回の基本演算（四則演算，大小比較，ビット演算...）を行うかで測る． 15 / 30

アルゴリズムの時間計算量アルゴリズムの時間計算量入力の大きさ n に対して，アルゴリズムが最大で何回の基本演算（四則演算，大小比較，ビット演算...）を行うかで測る．多項式時間高々 n の多項式回の基本演算
例: O(n) 時間，O(n2 ) 時間，O(n log n) 時間，O(n10000 ) 時間指数時間 O(2n ) 回，もしくはそれより大きい回数の基本演算 15 / 30

アルゴリズムの時間計算量アルゴリズムの時間計算量入力の大きさ n に対して，アルゴリズムが最大で何回の基本演算（四則演算，大小比較，ビット演算...）を行うかで測る．多項式時間高々 n の多項式回の基本演算
例: O(n) 時間，O(n2 ) 時間，O(n log n) 時間，O(n10000 ) 時間指数時間 O(2n ) 回，もしくはそれより大きい回数の基本演算「最大で」・・・アルゴリズムにとって最も苦手な入力を与えたときにかかる計算量を考える．（最悪時計算量） 15 / 30

線形計画 (LP) LP は以下の標準形で書くことができる: maximize n ∑ cj xj j=1
subject to n ∑ aij xj ≤ bi (i = 1, . . . , m) j=1 xj ≥ 0 (j = 1, . . . , n) 17 / 30

線形計画 (LP) LP は以下の標準形で書くことができる: maximize n ∑ maximize c⊤ x
subject to Ax ≤ b cj xj j=1 subject to n ∑ x≥0 aij xj ≤ bi (i = 1, . . . , m) j=1 xj ≥ 0 (j = 1, . . . , n) • A: m × n 行列 • b: m 次元ベクトル • c: n 次元ベクトル • x: n 次元決定変数 17 / 30

双対問題・強双対定理主問題 (P) 双対問題 (D) maximize c⊤ x subject to
Ax ≤ b x≥0 minimize b⊤ y subject to A⊤ y ≥ c y≥0 18 / 30

双対問題・強双対定理主問題 (P) 双対問題 (D) maximize c⊤ x subject to
Ax ≤ b x≥0 minimize b⊤ y subject to A⊤ y ≥ c y≥0 定理 (強双対定理) 主問題 (P) と双対問題 (D) がともに実行可能ならば，主問題 (P) に最適解 x∗ ，双対問題 (D) に最適解 y ∗ が存在して c⊤ x∗ = b⊤ y ∗ が成り立つ． 18 / 30

相補性条件補題主問題 (P) の実行可能解 x と双対問題 (D) の実行可能解 y
に対し，x と y がそれぞれの最適解 ⇐⇒ (A⊤ y − c)⊤ x = 0 かつ (b − Ax)⊤ y = 0 主問題 (P) max c⊤ x s.t. Ax ≤ b x≥0 双対問題 (D) min b⊤ y s.t. A⊤ y ≥ c y≥0 19 / 30

相補性条件補題主問題 (P) 主問題 (P) の実行可能解 x と双対問題 (D)
の実行可能解 y に対し，x と y がそれぞれの最適解 ⇐⇒ (A⊤ y − c)⊤ x = 0 かつ (b − Ax)⊤ y = 0 max c⊤ x s.t. Ax ≤ b x≥0 (証明) 実行可能解 (x, y) に対して， c⊤ x ≤ (A⊤ y)⊤ x = y ⊤ (Ax) ≤ y ⊤ b が常に成り立つ（弱双対性）．双対問題 (D) min b⊤ y s.t. A⊤ y ≥ c y≥0 19 / 30

相補性条件補題主問題 (P) 主問題 (P) の実行可能解 x と双対問題 (D)
の実行可能解 y に対し，x と y がそれぞれの最適解 ⇐⇒ (A⊤ y − c)⊤ x = 0 かつ (b − Ax)⊤ y = 0 max c⊤ x s.t. Ax ≤ b x≥0 (証明) 実行可能解 (x, y) に対して，双対問題 (D) c⊤ x ≤ (A⊤ y)⊤ x = y ⊤ (Ax) ≤ y ⊤ b が常に成り立つ（弱双対性）． ⊤ ⊤ (x, y) が最適解ならば，強双対定理から c x = y b なので，途中の不等号はすべて等号．よって c⊤ x = (A⊤ y)⊤ x, が成り立つ．逆も同様． min b⊤ y s.t. A⊤ y ≥ c y≥0 y ⊤ (Ax) = y ⊤ b 19 / 30

相補性条件定理 (相補性条件) 主問題 (P) の実行可能解 x と双対問題 (D) の実行可能解
y に対し，x と y がそれぞれの最適解 { (A⊤ y − c)j xj = 0 (j = 1, . . . , n) ⇐⇒ (b − Ax)i yi = 0 (i = 1, . . . , m) 主問題 (P) max c⊤ x s.t. Ax ≤ b x≥0 双対問題 (D) min b⊤ y s.t. A⊤ y ≥ c y≥0 20 / 30

相補性条件定理 (相補性条件) 主問題 (P) 主問題 (P) の実行可能解 x と双対問題
(D) の実行可能解 y に対し，x と y がそれぞれの最適解 { (A⊤ y − c)j xj = 0 (j = 1, . . . , n) ⇐⇒ (b − Ax)i yi = 0 (i = 1, . . . , m) 双対問題 (D) (証明) min b⊤ y s.t. A⊤ y ≥ c ⊤ ⊤ (A y − c) x = 0, ⊤ (b − Ax) y = 0 において，A⊤ y − c ≥ 0，x ≥ 0，b − Ax ≥ 0，y ≥ 0 なので，各項は非負．よって各項は 0． max c⊤ x s.t. Ax ≤ b x≥0 y≥0 20 / 30

多面体と端点 LP の実行可能領域 P = {x ∈ Rn : Ax
≤ b, x ≥ 0} = {x ∈ Rn : [ ] [ ] A b x≤ } −I 0 Ã 3 P b̃ は多面体 (polyhedron) と呼ばれる凸集合． 1 補題多面体 P の端点を x とする．このとき，次を満たす大きさ n の行部分集合 S が存在する． 1 • Ã から S に対応する行を抜き出した部分行列 ÃS は正則 • x は線形方程式 (ÃS )x = b̃S の（一意）解．ここで， b̃S は b から S に対応する行を抜き出したベクトル． 21 / 30

例 x2 P:  x1 + 2x2 ≤ 6 
  2x + x ≤ 6 1 2  x1 ≥ 0    x2 ≥ 0 x1 +2 x2 ≤6 (2, 2) 2x 1 x1 ≥ 0 2 P +x ≤6 で定まる R2 の多面体     1 2 6 2  6 1    Ã =  −1 0  , b̃ = 0 0 −1 0 (0, 3) (0, 0) x2 ≥ 0 x1 (3, 0) 22 / 30

LP を使った組合せ最適化問題の解法？ 1 組合せ最適化問題を 0–1 整数計画問題 (IP) として定式化する 2 IP
の 0–1 制約を落として得られる LP を解く 3 もし 0–1 成分の LP 最適解が得られたら，それは元の IP の最適解でもあるので，問題が解けた（ラッキー！）これがうまくいくための十分条件は？ → 完全単模行列 24 / 30

例：二部マッチング重み付き二部マッチング問題入力 G = (V ; E): 二部グラフ，枝重み we
(e ∈ E ) 出力 G の最大重みマッチング M 25 / 30

(e ∈ E ) 出力 G の最大重みマッチング M 1 4 2 5 3 IP 定式化 maximize ∑ max w⊤ x w e xe s.t. e∈E subject to ∑ x14 + x15 ≤1 x24 + x25 ≤1 xe ≤ 1 (i ∈ V ) x34 x14 + x24 + x34 ≤1 ≤1 xe ∈ {0, 1} (e ∈ E) x15 + x25 ≤1 e∈δ(i) x14 , x15 , x24 , x25 , x34 ∈ {0, 1} 25 / 30

(e ∈ E ) 出力 G の最大重みマッチング M 1 4 2 5 3 LP 定式化 maximize ∑ max w⊤ x w e xe x14 + x15 ≤1 x24 + x25 (i ∈ V ) ≤1 x34 x14 + x24 + x34 ≤1 ≤1 (e ∈ E) x15 + x25 ≤1 s.t. e∈E subject to ∑ xe ≤ 1 e∈δ(i) xe ≥ 0 実は，係数行列の完全単模性により常に 0–1 の LP 最適解をもつ！ x14 , x15 , x24 , x25 , x34 ∈ {0, 1} 25 / 30

完全単模行列定義 (完全単模行列) def m × n 行列 A が完全単模行列
⇐⇒ A のすべての小行列式 ∈ {0, ±1} 例   −1 1 0 0 −1 [ ] 1 0  1 0 0 −1 0   , 0 1  0 −1 1 0 0  0 0 −1 1 1 26 / 30

例: 二部マッチング補題二部マッチングの LP の係数行列 A は完全単模行列． 1 4
2 5 3 x14 1 1 2  0 3  0 4 1 5 0 x15 1 0 0 0 1 x24 0 1 0 1 0 x25 0 1 0 0 1 x34  0 0   1   1  0 27 / 30

例: 二部マッチング補題二部マッチングの LP の係数行列 A は完全単模行列． (証明) k
× k 小行列式 = 0, ±1 であることを，k に関する帰納法で示す． k = 1 のときは，A の成分は 0, 1 なので明らか． k > 1 とし，k × k 小行列 A′ を考える． 1 4 2 5 3 x14 1 1 2  0 3  0 4 1 5 0 x15 1 0 0 0 1 x24 0 1 0 1 0 x25 0 1 0 0 1 x34  0 0   1   1  0 27 / 30

× k 小行列式 = 0, ±1 であることを，k に関する帰納法で示す． k = 1 のときは，A の成分は 0, 1 なので明らか． k > 1 とし，k × k 小行列 A′ を考える． • A′ にゼロ列が含まれる場合: det A′ = 0 より成立． 1 4 2 5 3 x14 1 1 2  0 3  0 4 1 5 0 x15 1 0 0 0 1 x24 0 1 0 1 0 x25 0 1 0 0 1 x34  0 0   1   1  0 27 / 30

× k 小行列式 = 0, ±1 であることを，k に関する帰納法で示す． k = 1 のときは，A の成分は 0, 1 なので明らか． k > 1 とし，k × k 小行列 A′ を考える． • A′ にゼロ列が含まれる場合: det A′ = 0 より成立． • A′ に 1 が 1 つだけ含まれる列がある場合: 余因子展開すれば，(k − 1) × (k − 1) 小行列 A′′ を用いて， det A′ = ± det A′′ ．帰納法の仮定より det A′′ ∈ {0, ±1} なので OK． 1 4 2 5 3 x14 1 1 2  0 3  0 4 1 5 0 x15 1 0 0 0 1 x24 0 1 0 1 0 x25 0 1 0 0 1 x34  0 0   1   1  0 27 / 30

× k 小行列式 = 0, ±1 であることを，k に関する帰納法で示す． k = 1 のときは，A の成分は 0, 1 なので明らか． k > 1 とし，k × k 小行列 A′ を考える． • A′ にゼロ列が含まれる場合: det A′ = 0 より成立． • A′ に 1 が 1 つだけ含まれる列がある場合: 余因子展開すれば，(k − 1) × (k − 1) 小行列 A′′ を用いて， det A′ = ± det A′′ ．帰納法の仮定より det A′′ ∈ {0, ±1} なので OK． • A′ のどの列にも 1 が 2 つ含まれる場合: 左側の頂点に +1，右側の頂点に −1 をおいた行ベクトル v を考えると， vA′ = 0．よって，A′ は正則ではないので，det A′ = 0． 1 4 2 5 3 x14 1 1 2  0 3  0 4 1 5 0 x15 1 0 0 0 1 x24 0 1 0 1 0 x25 0 1 0 0 1 x34  0 0   1   1  0 27 / 30

整数多面体定義 (整数多面体) 全ての端点が整数ベクトルである多面体を整数多面体と呼ぶ． x2 x2 x1 整数多面体 x1 整数多面体でない多面体
28 / 30

完全単模行列と整数多面体定理完全単模行列 A と整数ベクトル b が定める多面体 P = {x
∈ Rn : Ax ≤ b, x ≥ 0} は整数多面体． 29 / 30

∈ Rn : Ax ≤ b, x ≥ 0} は整数多面体． (証明) x を P の端点とする．x は，(Ã, b̃) から n 行を抜き出して得られる正則行列 A′ と部分ベクトル b′ に対して，線形方程式 A′ x = b′ の解 x = (A′ )−1 b′ として得られる． 29 / 30

∈ Rn : Ax ≤ b, x ≥ 0} は整数多面体． (証明) x を P の端点とする．x は，(Ã, b̃) から n 行を抜き出して得られる正則行列 A′ と部分ベクトル b′ に対して，線形方程式 A′ x = b′ の解 x = (A′ )−1 b′ として得られる．クラーメルの公式より， (A′ )−1 ij = ∆j,i A′ ∈ {0, ±1} det A′ ※ ∆j,i A′ = A′ の (j, i) 余因子 b′ は整数ベクトルなので，(A′ )−1 b′ も整数ベクトル． 29 / 30

完全単模行列と LP の整数性定理 A が完全単模行列，b が整数ベクトルである主問題 (P) を考える．もし (P)
が最適解をもつならば，(P) に整数ベクトルの最適解が存在する．主問題 (P) c⊤ x s.t. Ax ≤ b max x≥0 30 / 30

完全単模行列と LP の整数性定理 A が完全単模行列，b が整数ベクトルである主問題 (P) を考える．もし (P)
が最適解をもつならば，(P) に整数ベクトルの最適解が存在する．主問題 (P) c⊤ x s.t. Ax ≤ b max x≥0 (証明) 前定理より，(P) の実行可能領域 P は整数多面体である．いま， (P) が最適解をもつので，特に P の端点である最適解が存在する．整数多面体の定義より，これは整数ベクトル． 30 / 30

組合せ最適化特論第 2 回（二部マッチング①）担当: 相馬輔 2026/05/07 1 /
26

目次 1. 二部マッチングの最大最小定理・ LP の整数性（復習）・ Kőnig–Egerváry の定理 2.
重みなし二部マッチング・増加道アルゴリズム・ Kőnig–Egerváry の定理再訪 3. 重み付き二部マッチング・相補性条件・ハンガリー法 2 / 26

二部マッチング重み付き二部マッチング問題入力 G = (V ; E) ∑: 二部グラフ，枝重み
we (e ∈ E ) 出力 w(M ) := e∈M we が最大のマッチング M 4 / 26

we (e ∈ E ) 出力 w(M ) := e∈M we が最大のマッチング M 1 4 2 5 3 IP 定式化 maximize ∑ max w⊤ x w e xe s.t. e∈E subject to ∑ xe ≤ 1 (i ∈ V ) e∈δ(i) xe ∈ {0, 1} (e ∈ E) x14 + x15 ≤1 x24 + x25 ≤1 x34 ≤1 x14 + x24 + x34 ≤1 x15 + x25 ≤1 x14 , x15 , x24 , x25 , x34 ∈ {0, 1} 4 / 26

we (e ∈ E ) 出力 w(M ) := e∈M we が最大のマッチング M 1 4 2 5 3 LP 定式化 maximize ∑ max w⊤ x w e xe s.t. e∈E subject to ∑ xe ≤ 1 (i ∈ V ) e∈δ(i) xe ≥ 0 (e ∈ E) 係数行列の完全単模性により常に 0–1 の LP 最適解をもつ！ x14 + x15 ≤1 x24 + x25 ≤1 x34 ≤1 x14 + x24 + x34 ≤1 x15 + x25 ≤1 x14 , x15 , x24 , x25 , x34 ∈ {0, 1} 4 / 26

二部マッチング多面体マッチング M の特性ベクトル (characteristic vector) 1M ∈ {0, 1}E
を次のように定める: { 1 (e ∈ M ) (1M )e = 0 (e ∈ / M) ※ χM と書く流儀もある二部マッチング多面体: P = conv{1M : M は G のマッチング } 定理二部マッチング多面体は次の線形不等式系で表される． ∑ xe ≤ 1 (i ∈ V ) e∈δ(i) xe ≥ 0 (e ∈ E) 5 / 26

二部マッチングの双対問題主問題 (P) max ∑ w e xe e∈E s.t.
∑ 双対問題 (D) ∑ min yi i∈V xe ≤ 1 (i ∈ V ) e∈δ(i) s.t. yi + yj ≥ we (e = ij ∈ E) y≥0 x≥0 双対問題 (D) の係数行列も完全単模．よって，枝重み we (e ∈ E ) が整数なら，(D) は整数最適解をもつ． 6 / 26

Kőnig–Egerváry の定理 G = (V + , V − ;
E) を V + , V − を頂点集合とする二部グラフとする．定義 S ⊆ V + , T ⊆ V − が頂点被覆 def ⇐⇒ 任意の枝 e = ij ∈ E に対し，i ∈ S または j ∈ T. T S 7 / 26

Kőnig–Egerváry の定理 G = (V + , V − ;
E) を V + , V − を頂点集合とする二部グラフとする．定義 S ⊆ V + , T ⊆ V − が頂点被覆 def ⇐⇒ 任意の枝 e = ij ∈ E に対し，i ∈ S または j ∈ T. T S 補題 (弱双対性) 任意のマッチング M と頂点被覆 (S, T ) に対し，|M | ≤ |S| + |T |. (証明) M は端点を共有しないので，M を被覆するには少なくとも |M | 個の頂点が必要． 7 / 26

Kőnig–Egerváry の定理先の LP において，w ≡ 1 の場合を考えると，整数性と強双対定理から以下の定理が得られる．定理
(Kőnig–Egerváry) 二部グラフ G において，次の最大最小定理が成り立つ． max M : マッチング |M | = min (S, T ): 頂点被覆 |S| + |T | 8 / 26

例右の二部グラフにおいて， 9 / 26

例右の二部グラフにおいて， • 最大のマッチングは |M | = 5 9 /
26

例右の二部グラフにおいて， • 最大のマッチングは |M | = 5 • 最小の頂点被覆は
|S| + |T | = 5 S 一般に，二部グラフにおいてマッチング M が最大であることを示すには， |M | = |S| + |T | T を満たす頂点被覆 (S, T ) を提示すれば良い． 9 / 26

例右の二部グラフにおいて， • 最大のマッチングは |M | = 5 • 最小の頂点被覆は
|S| + |T | = 5 S 一般に，二部グラフにおいてマッチング M が最大であることを示すには， |M | = |S| + |T | T を満たす頂点被覆 (S, T ) を提示すれば良い．そのような頂点被覆は，M の最適性の証拠といえる（良い特徴づけ; good characterization） 9 / 26

増加道 M : G のマッチング定義 def パス P が（M
に対する）増加道 ⇐⇒ 1 P において E \ M と M の枝が交互に現れる． 2 P の始点と終点は M に接続していない頂点． ∈M ∈ /M |M | = 3 11 / 26

に対する）増加道 ⇐⇒ 1 P において E \ M と M の枝が交互に現れる． 2 P の始点と終点は M に接続していない頂点． |M | = 3 ∈M ∈ /M ↓ 反転 |M | = 4 11 / 26

に対する）増加道 ⇐⇒ 1 P において E \ M と M の枝が交互に現れる． 2 P の始点と終点は M に接続していない頂点． |M | = 3 ∈M ∈ /M ↓ 反転 |M | = 4 ∴ M が最大マッチング =⇒ 増加道は存在しない 11 / 26

増加道補題 M が最大でない =⇒ 増加道が存在． 12 / 26

増加道補題 M が最大でない =⇒ 増加道が存在． (証明) 2 つのマッチング M
, M ′ (|M | < |M ′ |) を取る．すると， M + M ′ の連結成分は交互道と長さ偶数のサイクルからなる．いま，|M | < |M ′ | より，M + M ′ の連結成分の中に，交互道で始点と終点が M の端点でないものが存在する．これは M に対する増加道． 12 / 26

増加道アルゴリズム補題より，以下のようなアルゴリズムが考えられる．増加道アルゴリズム 1: M ← ∅ とする． 2: while
M に対する増加道が存在する : 3: 増加道の 1 つを求めて P とする． 4: P に沿って枝を反転して，より大きなマッチング M を得る． 5: return M 増加道 P を A 時間で求められれば，全体は O(nA) 時間アルゴリズム． 13 / 26

有向グラフを用いた増加道探索マッチング M に対し，G の枝を V− V+ • M の枝は両向き，
• E \ M の枝は V + から V − 向きに向き付けた有向グラフを DM とする． DM 14 / 26

U− • E \ M の枝は V + から V − 向きに向き付けた有向グラフを DM とする．また， U− • U + := M に接続していない V + の頂点集合 • U − := M に接続していない V − の頂点集合とする． U+ DM 14 / 26

U− • E \ M の枝は V + から V − 向きに向き付けた有向グラフを DM とする．また， U− • U + := M に接続していない V + の頂点集合 • U − := M に接続していない V − の頂点集合とする． − 増加道 ←→ DM における U から U への有向パス + ∴ 幅優先探索により O(m) 時間で増加道が求められる (m = |E|) U+ DM 14 / 26

例 G 15 / 26

例 U− U+ G DM 15 / 26

例 U− U+ G U− DM 15 / 26

例 U− U+ G DM 15 / 26

例 U− U+ G DM 【終了】 15 / 26

Kőnig–Egerváry の定理再訪 max M : マッチング |M | = min
(S, T ): 頂点被覆 |S| + |T | 定理アルゴリズムが停止したときの DM において，U + から到達可能な頂点全体を X とする．このとき S := V + \ X, T := V − ∩ X S U− とすると，(S, T ) は最小頂点被覆． X U+ T 16 / 26

(S, T ): 頂点被覆 |S| + |T | 定理アルゴリズムが停止したときの DM において，U + から到達可能な頂点全体を X とする．このとき S := V + \ X, T := V − ∩ X S U− とすると，(S, T ) は最小頂点被覆． (証明) 全ての枝は右向きに進めるので，(S, T ) は定義から頂点被覆．また，増加道が存在しないので，X ∩ U − = ∅. ゆえに (S, T ) の全ての頂点は M の枝を 1 本だけ被覆して X いるので，|S| + |T | = |M |. U+ T 16 / 26

(S, T ): 頂点被覆 |S| + |T | 定理アルゴリズムが停止したときの DM において，U + から到達可能な頂点全体を X とする．このとき S := V + \ X, T := V − ∩ X S U− とすると，(S, T ) は最小頂点被覆． (証明) 全ての枝は右向きに進めるので，(S, T ) は定義から頂点被覆．また，増加道が存在しないので，X ∩ U − = ∅. ゆえに (S, T ) の全ての頂点は M の枝を 1 本だけ被覆して X いるので，|S| + |T | = |M |. Kőnig–Egerváry の定理の，LP を使わないアルゴリズム的証明が得られた． U+ T 16 / 26

重みなし二部マッチング（まとめ）定理二部グラフにおいて， • 増加道アルゴリズムは最大マッチング M を O(mn) 時間で求める．
(m = |E|, n = |V |) • 同時に，|M | = |S| + |T | を満たす最小頂点被覆 (S, T ) も求められる． 17 / 26

重み付き二部（完全）マッチング def マッチング M が完全 ⇐⇒ 全ての頂点が M に接続 ⇐⇒
2|M | = |V | 重み付き二部完全マッチング問題 + − 入力 G = (V ; E) ∑: 二部グラフ (|V | = |V | = n/2)，枝重み we (e ∈ E ) 出力 w(M ) := e∈M we が最大の完全マッチング M ※ 以下，G は少なくとも 1 つの完全マッチングを持つとする． 19 / 26

重み付き二部（完全）マッチング def マッチング M が完全 ⇐⇒ 全ての頂点が M に接続 ⇐⇒
2|M | = |V | 重み付き二部完全マッチング問題 + − 入力 G = (V ; E) ∑: 二部グラフ (|V | = |V | = n/2)，枝重み we (e ∈ E ) 出力 w(M ) := e∈M we が最大の完全マッチング M ※ 以下，G は少なくとも 1 つの完全マッチングを持つとする．主問題 (P) max ∑ w e xe e∈E s.t. ∑ 双対問題 (D) ∑ min yi =: y(V ) i∈V xe = 1 (i ∈ V ) s.t. yi + yj ≥ we (e = ij ∈ E) e∈δ(i) x≥0 19 / 26

最適性条件補題 (最適性条件) M ⊆ E , y ∈ RV
が最適解 ⇐⇒ 1 M は完全マッチング 2 y は (D) の実行可能解 3 yi + yj = w e (e = ij ∈ M ) (相補性条件) 主問題 (P) max ∑ w e xe e∈E s.t. ∑ xe = 1 (i ∈ V ) e∈δ(i) x≥0 双対問題 (D) ∑ min yi =: y(V ) i∈V s.t. yi + yj ≥ we (e ∈ E) 20 / 26

最適性条件補題 (最適性条件) M ⊆ E , y ∈ RV
が最適解 ⇐⇒ 1 M は完全マッチング 2 y は (D) の実行可能解 3 yi + yj = w e (e = ij ∈ M ) (相補性条件) 以下， • (D) の実行可能解を w 被覆 • ③を満たす枝をタイトな枝という．主問題 (P) max ∑ w e xe e∈E s.t. ∑ xe = 1 (i ∈ V ) e∈δ(i) x≥0 双対問題 (D) ∑ min yi =: y(V ) i∈V s.t. yi + yj ≥ we (e ∈ E) 20 / 26

ハンガリー法 ②③を満たすマッチング M と w 被覆 y を保持し，①を満たすまで更新するアルゴリズム．定義
w 被覆 y に対し，G の部分グラフ Gy = (V + , V − , Ey ) を Ey = {e = ij ∈ E : yi + yj = we } と定める．つまり，Gy は y に関しタイトな枝のみ残したグラフ．補題 Gy に完全マッチングが存在すれば，それは最大重みマッチング． (証明) 最適性条件！ 21 / 26

ハンガリー法 Gy に完全マッチングが存在しなかったら？ −→ y を更新し，(D) の目的関数値を改善できる． 22 / 26

ハンガリー法 Gy に完全マッチングが存在しなかったら？ −→ y を更新し，(D) の目的関数値を改善できる．補題 DM (y):
Gy に対する重みなしマッチングで使う有向グラフ X : DM (y) における U + から到達可能な頂点全体 ε := min{yi + yj − we : e = ij ∈ E, i ∈ V + ∩ X, j ∈ V − \ X} とする．y ′ を  +  yi − ε (i ∈ V ∩ X) yi′ = yi + ε (i ∈ V − ∩ X)  y (それ以外) i X 4 −ε +ε −ε +ε 2 3 −ε 2 0 0 とすると，y ′ は w 被覆で，y ′ (V ) < y(V ) を満たす． 22 / 26

補題の証明 ε := min{yi + yj − we: e =
ij ∈ E, i ∈ V + ∩ X, j ∈ V − \ X} +  yi − ε (i ∈ V ∩ X) yi′ = yi + ε (i ∈ V − ∩ X)   yi (それ以外) y ′ が w 被覆であること • 制約 yi + yj ≥ we (e = ij ∈ E ) が更新後に破られる可能性があるのは， i ∈ V + ∩ X , j ∈ V − \ X の場合のみ． • ε の定義より実行可能性は保たれる． 23 / 26

補題の証明 ε := min{yi + yj − we: e =
ij ∈ E, i ∈ V + ∩ X, j ∈ V − \ X} +  yi − ε (i ∈ V ∩ X) yi′ = yi + ε (i ∈ V − ∩ X)   yi (それ以外) y ′ が w 被覆であること • 制約 yi + yj ≥ we (e = ij ∈ E ) が更新後に破られる可能性があるのは， i ∈ V + ∩ X , j ∈ V − \ X の場合のみ． • ε の定義より実行可能性は保たれる． y ′ (V ) < y(V ) であること • y ′ (V ) = y(V ) − ε(|V + ∩ X| − |V − ∩ X|)． • いま，Gy に完全マッチングが存在しないので，|V + \ X| + |V − ∩ X| < n/2. −→ |V + ∩ X| − |V − ∩ X| > 0. • よって，ε > 0 を示せば良い．X は Gy の到達可能集合なので，任意の枝 e = ij ∈ E s.t. i ∈ V + ∩ X , j ∈ V − \ X はタイトでない．ゆえに yi + yj − we > 0 が成り立つ． 23 / 26

ハンガリー法 1: yi := maxe∈δ(i) we (i ∈ V +
), yj := 0 (j ∈ V − ) とする． // y は自明な w 被覆 2: while True : 3: Gy の（重みなし）最大マッチング M を求める． // O(mn) 時間 4: if M が完全マッチング : 5: return M // 相補性条件より，M は最大重みマッチング 6: else // w 被覆 y を更新 + 7: X を DM (y) における U から到達可能な頂点全体とする． 8: ε := min{yi + yj − wij : i ∈ V + ∩ X, j ∈ V − \ X} 9: yi ← yi − ε (i ∈ V + ∩ X ), yj ← yj + ε (j ∈ V − ∩ X ) 24 / 26

例 5 4 4 2 1 5 2 G 25
/ 26

例 5 4 X 5 0 4 0 5 0
4 2 1 5 2 G y(V ) = 14, 25 / 26

例 X 5 −ε 5 4 4 2 1 5
2 G 4 5 +ε −ε −ε 0 0 0 y(V ) = 14, ε = 1 25 / 26

例 X 5 −ε 5 4 4 2 1 5
2 G 4 5 +ε −ε −ε y(V ) = 14, ε = 1 4 1 0 X 3 0 4 0 0 0 y(V ) = 12, 25 / 26

例 X 5 −ε 5 4 4 2 1 5
2 G 4 5 +ε −ε −ε y(V ) = 14, ε = 1 0 +ε 4 −ε 0 X 3 0 4 −ε 1 0 0 y(V ) = 12, ε = 1 25 / 26

例 X 5 −ε 5 4 4 2 1 5
2 G 4 5 +ε −ε −ε y(V ) = 14, ε = 1 0 +ε 4 −ε 0 X 3 0 4 −ε y(V ) = 12, ε = 1 1 X 4 2 0 2 0 0 3 0 y(V ) = 11, 25 / 26

例 X 5 −ε 5 4 4 2 1 5
2 G 4 5 +ε −ε −ε y(V ) = 14, ε = 1 0 +ε 4 −ε 0 X 3 0 4 −ε y(V ) = 12, ε = 1 −ε 1 X 4 +ε −ε +ε 0 2 0 3 −ε 2 0 0 y(V ) = 11, ε = 1 25 / 26

例 X 5 −ε 5 4 4 4 2 1
5 5 2 G +ε −ε −ε y(V ) = 14, ε = 1 3 3 1 1 2 y(V ) = 10 0 0 +ε 4 −ε 0 X 3 0 4 −ε y(V ) = 12, ε = 1 −ε 1 X 4 +ε −ε +ε 0 2 0 3 −ε 2 0 0 y(V ) = 11, ε = 1 25 / 26

例 X 5 −ε 5 4 4 4 2 1
5 5 2 G +ε −ε −ε y(V ) = 14, ε = 1 3 3 1 1 0 +ε 4 −ε 0 X 3 0 4 −ε y(V ) = 12, ε = 1 −ε 1 X 4 +ε −ε +ε 0 2 0 3 −ε 2 0 0 y(V ) = 11, ε = 1 2 0 y(V ) = 10 = w(M ) 【終了】 25 / 26

ハンガリー法の計算量解析定理ハンガリー法は O(mn3 ) 時間で最大重み完全マッチングと最小 w 被覆を求める． (m =
|E|, n = |V |) 26 / 26

|E|, n = |V |) (証明) • アルゴリズムの実行中に |M | は減らない． −→ M は高々 n/2 回更新される． 26 / 26

|E|, n = |V |) (証明) • アルゴリズムの実行中に |M | は減らない． (∵) y が更新されて y ′ になったとき，Gy の最大マッチング M は Gy′ でもマッチング． −→ M は高々 n/2 回更新される． 26 / 26

|E|, n = |V |) (証明) • アルゴリズムの実行中に |M | は減らない． (∵) y が更新されて y ′ になったとき，Gy の最大マッチング M は Gy′ でもマッチング． −→ M は高々 n/2 回更新される． • また，|M | が増えず y だけが更新されるとき，ε の定義の min を達成する枝により，到達可能集合 X が真に拡大する． −→ 高々 n 回の y の更新後に，|M | は増える． 26 / 26

|E|, n = |V |) (証明) • アルゴリズムの実行中に |M | は減らない． (∵) y が更新されて y ′ になったとき，Gy の最大マッチング M は Gy′ でもマッチング． −→ M は高々 n/2 回更新される． • また，|M | が増えず y だけが更新されるとき，ε の定義の min を達成する枝により，到達可能集合 X が真に拡大する． −→ 高々 n 回の y の更新後に，|M | は増える． ∴全体では O(n2 ) 回の反復． 26 / 26

組合せ最適化特論第 3 回（二部マッチング②）担当: 相馬輔 2026/05/14 1 /
29

目次 1. 最短路問題・定義・負閉路とポテンシャル 2. 逐次最短路法と主双対法・
逐次最短路法・主双対法 3. 最適性条件からの見方・ポテンシャル最適性条件・閉路最適性条件・アルゴリズム再訪 2 / 29

最短路問題 G = (V, A): 有向グラフ s, t ∈ V
: 始点・終点 ℓ : A → R: 枝長 s t P : s–t 路（s から t へ行く経路で，同じ枝や頂点を複数回通っても良い）に対し， ∑ ℓ(P ) := ℓ(a) a∈A(P ) を P の長さとする．最短路問題 s–t 路 P で長さ ℓ(P ) 最小のものを求めよ． 4 / 29

最短路問題と負閉路 s を固定する．任意の t に対して，最短路は存在するか？補題 G の任意の頂点は s から到達可能であるとする．このとき，以下は
同値: • 任意の t に対し s–t 最短路が存在 • 有向閉路 C で ℓ(C) < 0 なるもの（負閉路）は存在しない． 5 / 29

ポテンシャル定義 (ポテンシャル) p : V → R が枝長 ℓ
に関する（実行可能）ポテンシャル def ⇐⇒ p(j) − p(i) ≤ ℓ(a) (a = ij ∈ A) 補題 G の任意の頂点は s から到達可能とする．このとき，以下は同値: 1 任意の t に対し s–t 最短路が存在 2 ポテンシャル p : V → R が存在 3 負閉路が存在しない 6 / 29

ポテンシャル 1 任意の t に対し s–t 最短路が存在 2 ポテンシャル p
: V → R が存在 3 負閉路が存在しない (証明) ① =⇒ ②: p(t) := (s–t 最短路長) とおく．任意の枝 a = ij ∈ A に対し，図より p(j) ≤ p(i) + ℓ(a). 7 / 29

: V → R が存在 3 負閉路が存在しない (証明) ① =⇒ ②: p(t) := (s–t 最短路長) とおく．任意の枝 a = ij ∈ A に対し，図より p(j) ≤ p(i) + ℓ(a). ② =⇒ ③: 任意の有向閉路 C : v0 → v1 → · · · → vk = v0 に対して， ℓ(C) = k ∑ i=1 ℓ(vi−1 vi ) ≥ k ∑ (p(vi ) − p(vi−1 )) = 0. i=1 7 / 29

: V → R が存在 3 負閉路が存在しない (証明) ① =⇒ ②: p(t) := (s–t 最短路長) とおく．任意の枝 a = ij ∈ A に対し，図より p(j) ≤ p(i) + ℓ(a). ② =⇒ ③: 任意の有向閉路 C : v0 → v1 → · · · → vk = v0 に対して， ℓ(C) = k ∑ i=1 ℓ(vi−1 vi ) ≥ k ∑ (p(vi ) − p(vi−1 )) = 0. i=1 ③ =⇒ ①: すでにやった． 7 / 29

ポテンシャルの存在と負閉路定理有向グラフ G と枝長 ℓ : A → R
に対して，ポテンシャル p : V → R が存在 ⇐⇒ 負閉路が存在しない (証明) G に頂点 s を追加し，s から G の全ての頂点へ枝を追加したグラフを G′ とする．新しい枝の長さを 0 と定めて ℓ を拡張した枝長を， ℓ′ とする．このとき， (G′ , ℓ′ ) の負閉路 ⇐⇒ (G, ℓ) の負閉路 ∴ (G′ , ℓ′ ) に前補題を適用すればよい． 8 / 29

最短路問題のアルゴリズム単一の始点 s に対して，全ての t に関する最短路問題を同時に解くアルゴリズムが知られている: 一般の枝長 ℓ: Bellman–Ford
法 O(mn) 時間 ※負閉路がある場合は検出も可能非負の枝長 ℓ: Dijkstra 法 O(m + n log n) 時間 (n = |V |, m = |E|) これらは，s–t 最短路だけでなく，実行可能ポテンシャルも同時に求める． 9 / 29

重み付き二部マッチング重み付き二部マッチング問題入力 G = (V ; E) ∑: 二部グラフ，枝重み
we (e ∈ E ) 出力 w(M ) := e∈M we が最小のマッチング M 11 / 29

補助ネットワーク（復習）マッチング M に対し，G の枝を V− V+ • M の枝は両向き，
• E \ M の枝は V + から V − 向きに向き付けた有向グラフを DM とする． DM 12 / 29

U− • E \ M の枝は V + から V − 向きに向き付けた有向グラフを DM とする．また， U− • U + := M に接続していない V + の頂点集合 • U − := M に接続していない V − の頂点集合とする． U+ DM 12 / 29

U− • E \ M の枝は V + から V − 向きに向き付けた有向グラフを DM とする．また， U− • U + := M に接続していない V + の頂点集合 • U − := M に接続していない V − の頂点集合とする． − 増加道 ←→ DM における U から U への有向パス + ∴ 幅優先探索により O(m) 時間で増加道が求められる (m = |E|) U+ DM 12 / 29

逐次最短路法マッチング M に対し，DM の枝長 ℓM を { w(e) (a
= V + から V − 向きの e ∈ E) ℓM (a) := −w(e) (a = V − から V + 向きの e ∈ E) V− V+ U− と定める． U− U+ DM 13 / 29

逐次最短路法マッチング M に対し，DM の枝長 ℓM を { w(e) (a
= V + から V − 向きの e ∈ E) ℓM (a) := −w(e) (a = V − から V + 向きの e ∈ E) V− V+ U− と定める． U− （なぜこう定めるのか？）交互道 or 交互サイクル P に関して反転操作を行った後のマッチング M △P の重みが w(M △P ) = w(M ) + ℓM (P ) と書けて便利なので． U+ DM 13 / 29

逐次最短路法 w(M △P ) = w(M ) + ℓM (P
) より，ℓM (P ) 最小の増加道 P を選ぶのが良さそう逐次最短路法 1: M ← ∅ 2: while M に対する増加道が存在する : 3: 補助ネットワーク (DM , ℓM ) 上で U + –U − 最短路 P を求める 4: M ← M △P // 初期マッチング // Bellman–Ford 法で O(mn) 時間 // マッチング更新 M △P : M と P の対称差（P に沿って M の枝を反転） 14 / 29

逐次最短路法 w(M △P ) = w(M ) + ℓM (P
) より，ℓM (P ) 最小の増加道 P を選ぶのが良さそう逐次最短路法 1: M ← ∅ 2: while M に対する増加道が存在する : 3: 補助ネットワーク (DM , ℓM ) 上で U + –U − 最短路 P を求める 4: M ← M △P // 初期マッチング // Bellman–Ford 法で O(mn) 時間 // マッチング更新 M △P : M と P の対称差（P に沿って M の枝を反転）定理逐次最短路法で求まるマッチングを ∅ = M0 , M1 , · · · , Mµ とする．このとき，各 k = 0, 1, . . . , µ に対し，Mk は大きさ k のマッチングのうち重み最小である．また，大きさ µ + 1 以上のマッチングは存在しない． 14 / 29

逐次最短路法の証明定理逐次最短路法で求まるマッチングを ∅ = M0 , M1 , ·
· · , Mµ とする．このとき，各 k = 0, 1, . . . , µ に対し，Mk は大きさ k のマッチングのうち重み最小である． (証明) k に関する帰納法．k = 0 は自明． M が大きさ k の最小重みマッチングで，少なくとも 1 つ増加道をもつと仮定する． Claim. (DM , ℓM ) は U + –U − 最短路をもつ 15 / 29

· · , Mµ とする．このとき，各 k = 0, 1, . . . , µ に対し，Mk は大きさ k のマッチングのうち重み最小である． (証明) k に関する帰納法．k = 0 は自明． M が大きさ k の最小重みマッチングで，少なくとも 1 つ増加道をもつと仮定する． Claim. (DM , ℓM ) は U + –U − 最短路をもつ (∵) 負閉路が存在しないことを示せば良い．負閉路 C が存在したと仮定する．C は交互サイクルであるとしてよい．すると，M △C は大きさ k のマッチングで， w(M △C) = w(M ) + ℓM (C) < w(M ) となり，矛盾． 15 / 29

· · , Mµ とする．このとき，各 k = 0, 1, . . . , µ に対し，Mk は大きさ k のマッチングのうち重み最小である． (証明) k に関する帰納法．k = 0 は自明． M が大きさ k の最小重みマッチングで，少なくとも 1 つ増加道をもつと仮定する． Claim. (DM , ℓM ) は U + –U − 最短路をもつ P を U + –U − 最短路とし，M + := M △P を更新後のマッチングとする． Claim. 任意の大きさ k + 1 のマッチング N に対し，w(M + ) ≤ w(N ) 15 / 29

逐次最短路法の証明 M : 大きさ k の最小重みマッチング P = (DM ,
ℓM ) 上の U + –U − 最短路 M + := M △P : 更新後のマッチング Claim. 任意の大きさ k + 1 のマッチング N に対し，w(M + ) ≤ w(N ) (∵) M と N の対称差 M △N は，交互道と偶サイクルからなる．いま，|M | < |N | より，この中に M 増加道 Q が存在する． Q 16 / 29

逐次最短路法の証明 M : 大きさ k の最小重みマッチング P = (DM ,
ℓM ) 上の U + –U − 最短路 M + := M △P : 更新後のマッチング Claim. 任意の大きさ k + 1 のマッチング N に対し，w(M + ) ≤ w(N ) (∵) M と N の対称差 M △N は，交互道と偶サイクルからなる．いま，|M | < |N | より，この中に M 増加道 Q が存在する． Q P は最短路なので，ℓM (P ) ≤ ℓM (Q). また，N △Q は大きさ k のマッチングなので， w(M ) ≤ w(N △Q) = w(N ) − ℓM (Q). これらより， w(M + ) = w(M ) + ℓM (P ) ≤ w(N ) − ℓM (Q) + ℓM (P ) ≤ w(N ). 16 / 29

逐次最短路法の計算量計算量解析 • M の更新は µ 回 (µ = 最大マッチングの大きさ)
• 各更新は 1 回の (DM , ℓM ) 上の最短路問題 −→ Bellman–Ford 法で O(mn) 時間 (n = |V |, m = |E|) 定理 (伊理 (1960)) 逐次最短路法は，O(mnµ) 時間で，k = 0, 1, . . . , µ に対する大きさ k の最小重みマッチング Mk を求める． Cf. ハンガリー法 O(mn3 ) 時間 17 / 29

主双対法マッチング M とポテンシャル p の両方を保持することで，逐次最短路法の計算量を改善できる．定義 (簡約枝長) 枝長
ℓ : A → R のポテンシャル p : V → R に関する簡約枝長 ℓp : A → R を次のように定める: ℓp (a) := ℓ(a) + p(i) − p(j) (a = ij ∈ A) 観察 • 任意の s–t 路 P に対し， ℓp (P ) = ℓ(P ) + p(s) − p(t). 特に，ℓp に関する s–t 最短路 ⇐⇒ ℓ に関する s–t 最短路． • ℓp ≥ 0 . . . . . . . . . . . . . . . . . . . . . . . Bellman-Ford 法ではなく Dijkstra 法が使える！ 18 / 29

主双対法主双対法 1: M := ∅ // 初期マッチング 2: p(i)
:= 0 (i ∈ V + ), p(j) := mini∈δ(j) w(ij) (j ∈ V − ) // 初期ポテンシャル 3: while M に対する増加道が存在する : 4: 簡約枝長 ℓM,p に関する DM 上の U + –U − 最短路 P と最短路長関数 d を求める． // Dijkstra 法で O(m + n log n) 時間 5: M ← M △P , p ← p + d // マッチングとポテンシャル更新定理 (Edmonds–Karp (1970), 冨澤 (1971)) 主双対法で求まるマッチングを ∅ = M0 , M1 , · · · , Mµ とする（µ = 最大マッチングの大きさ）．このとき，各 k = 0, 1, . . . , µ に対し，Mk は大きさ k のマッチングのうち重み最小である．また，全体の計算量は O((m + n log n)µ) 時間． 19 / 29

主双対法の証明次の補題を示せば，あとは逐次最短路法の定理から従う．補題主双対法における p は，常に (DM , ℓM )
上のポテンシャル． 20 / 29

上のポテンシャル． (証明) p+ := p + d とする．(d : V → R ... (DM , ℓM,p ) 上の（U + からの）最短路長関数) Claim. p+ は (DM , ℓM ) のポテンシャル 20 / 29

上のポテンシャル． (証明) p+ := p + d とする．(d : V → R ... (DM , ℓM,p ) 上の（U + からの）最短路長関数) Claim. p+ は (DM , ℓM ) のポテンシャル (∵) d は (DM , ℓM,p ) のポテンシャルなので，任意の DM の枝 a = ij に対し， d(j) − d(i) ≤ ℓM,p (a) = ℓM (a) + p(i) − p(j) が成り立つ．移項すると p+ (j) − p+ (i) ≤ ℓM (a). 20 / 29

上のポテンシャル． (証明) p+ := p + d とする．(d : V → R ... (DM , ℓM,p ) 上の（U + からの）最短路長関数) Claim. p+ は (DM , ℓM ) のポテンシャル (∵) d は (DM , ℓM,p ) のポテンシャルなので，任意の DM の枝 a = ij に対し， d(j) − d(i) ≤ ℓM,p (a) = ℓM (a) + p(i) − p(j) が成り立つ．移項すると p+ (j) − p+ (i) ≤ ℓM (a). Claim. M + := M △P に対し，p+ は (DM + , ℓM + ) のポテンシャル 20 / 29

上のポテンシャル． (証明) p+ := p + d とする．(d : V → R ... (DM , ℓM,p ) 上の（U + からの）最短路長関数) Claim. p+ は (DM , ℓM ) のポテンシャル (∵) d は (DM , ℓM,p ) のポテンシャルなので，任意の DM の枝 a = ij に対し， d(j) − d(i) ≤ ℓM,p (a) = ℓM (a) + p(i) − p(j) が成り立つ．移項すると p+ (j) − p+ (i) ≤ ℓM (a). Claim. M + := M △P に対し，p+ は (DM + , ℓM + ) のポテンシャル (∵) 最短路 P 上の枝 a = ij では，上の不等式で等号が成立: d(j) − d(i) = ℓM,p (a) ⇐⇒ p+ (j) − p+ (i) = ℓM (a) よって，M の更新により P の枝が反転されても，p+ がポテンシャルであることは保たれる． 20 / 29

最適性条件からの見方ハンガリー法，逐次最短路法，主双対法は，どれも同じアルゴリズムの異なる姿と思える． 22 / 29

最適性条件からの見方ハンガリー法，逐次最短路法，主双対法は，どれも同じアルゴリズムの異なる姿と思える．以下，最小重み完全マッチングを考えよう． def マッチング M が完全
⇐⇒ 全ての頂点が M に接続 ⇐⇒ 2|M | = |V | 重み付き二部完全マッチング問題 + − 入力 G = (V ; E) ∑: 二部グラフ (|V | = |V | = n/2)，枝重み we (e ∈ E ) 出力 w(M ) := e∈M we が最小の完全マッチング M ※ 以下，G は少なくとも 1 つの完全マッチングを持つとする． 22 / 29

双対変数とポテンシャル主問題 (P) ∑ min w e xe e∈E s.t.
∑ 双対問題 (D) ∑ yi =: y(V ) max i∈V xe = 1 (i ∈ V ) s.t. yi + yj ≤ we (e = ij ∈ E) e∈δ(i) x≥0 双対変数 y ∈ RV s.t. yi + yj ≤ we (e = ij ∈ E ) ↕ ポテンシャル p : V → R s.t. p(j) − p(i) ≤ we (e = ij ∈ E ) 23 / 29

最適性条件のポテンシャルを用いた書き換え最適性条件 (復習) M ⊆ E , y ∈ R
が最適解 ⇐⇒ 1 M は完全マッチング 2 y は (D) の実行可能解 (e = ij ∈ M ) 3 yi + yj = w e 主問題 (P) V 補題 M ⊆ E , p : V → R が最適解 ⇐⇒ 1 M は完全マッチング 2 p は (DM , ℓM ) のポテンシャル min ∑ w e xe e∈E s.t. ∑ xe = 1 (i ∈ V ) e∈δ(i) x≥0 双対問題 (D) ∑ max yi =: y(V ) i∈V s.t. yi + yj ≤ we (e ∈ E) 24 / 29

最適性条件のポテンシャルを用いた書き換え最適性条件 (復習) 補題 M ⊆ E , y ∈
R が最適解 ⇐⇒ M ⊆ E , p : V → R が最適解 ⇐⇒ V 1 2 3 M は完全マッチング y は (D) の実行可能解 yi + yj = we (e = ij ∈ M ) 1 2 M は完全マッチング p は (DM , ℓM ) のポテンシャル (証明) DM においては，M の枝は両向きであることに注意する．p がポテンシャルならば，e = ij ∈ M に対し， → p(j) − p(i) ≤ ℓM (− e ) = we ← − p(i) − p(j) ≤ ℓM ( e ) = −we が成り立つので，対応する y は③を満たす．逆も同様． 25 / 29

ポテンシャル最適性条件・閉路最適性条件補題完全マッチング M に対し，以下は同値: 1 M は最小重み完全マッチング 2 (DM
, ℓM ) のポテンシャル p が存在 3 (DM , ℓM ) に負閉路は存在しない (証明) ① ⇐⇒ ②: M が最適 ⇐⇒ ∃p s.t. (M, p) は最適性条件を満たす ② ⇐⇒ ③: 最短路問題のところでやった． 26 / 29

ハンガリー法（ポテンシャル版）ハンガリー法 1: p(i) := 0 (i ∈ V +
), p(j) := mine∈δ(j) we (j ∈ V − ) とする． // p は初期ポテンシャル 2: while True : 3: Gp の（重みなし）最大マッチング M を求める． // O(mn) 時間 4: if M が完全マッチング : 5: return M // 相補性条件より，M は最小重みマッチング 6: else // ポテンシャル p を更新 + 7: X を DM (p) における U から到達可能な頂点全体とする． + − 8: ε := min{w { e + p(i) − p(j) : e = ij, i ∈ V ∩ X, j ∈ V \ X} 9: p(i) ← p(i) − ε (i ∈ X) p(i) (otherwise) 27 / 29

ハンガリー法（ポテンシャル版）ハンガリー法 1: p(i) := 0 (i ∈ V +
), p(j) := mine∈δ(j) we (j ∈ V − ) とする． 2: while True : 4: 5: 6: 7: 8: 9: // p は初期ポテンシャル if Gp が完全マッチング (say M ) をもつ : return M // 相補性条件より，M は最小重みマッチング else // ポテンシャル p を更新 Gp の最小頂点被覆 (S, T ) を求める // |S| + |T | < n/2 ε := min{w + p(i) − p(j) : e = ij ∈ E s.t. (S, T ) に被覆されていない } { e p(i) ← p(i) − ε (i ∈ (V + \ S) ∪ T ) p(i) (otherwise) 最後の反復以外，M を使っていない！実質的に保持しているのはポテンシャル p のみ． 27 / 29

逐次最短路法，主双対法，ハンガリー法逐次最短路法主双対法ハンガリー法マッチング M (マッチングは保持しない) (ポテンシャルは陰に保持) マッチング M
ポテンシャル p 更新方法最短路 (Bellman–Ford) 最短路 (Dijkstra) 幅優先探索計算量 O(mn2 ) O((m + n log n)n) O(mn3 ) 変数ポテンシャル p どれもポテンシャル（双対変数）p : V → R を保持し，マッチング M が完全になるまで更新するアルゴリズムとみなせる． 28 / 29

まとめ: 二部マッチングまとめ • 重みなし: 増加道アルゴリズム • 重みあり: 逐次最短路法，主双対法，ハンガリー法 •
双対変数と最短路問題のポテンシャルの関係 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ネットワークフローやマトロイド交差へその他のアルゴリズム √ • Hopcroft–Karp–Karzanov 法 (1973): 重みなし O(m n) 時間 • 重みあり: m1+o(1) 時間（JACM 2025 1 , 最小費用流） 1 L. Chen, R. Kyng, Y. P. Liu, R. Peng, M. P. Gutenberg, and S. Sachdeva, “Maximum Flow and Minimum-Cost Flow in Almost-Linear Time”, JACM, 2025. 29 / 29

組合せ最適化特論第 4 回（最大流①）担当: 相馬輔 2026/5/21 1 /
36

目次 1. 最大流問題・定義・最大流最小カット定理・整数性 2.
最大流を用いたモデリング・ Menger の定理・二部マッチング・ Baseball Elimination ・最密部分グラフ ※アルゴリズムは次回 6 / 36

最大流問題: 定義 G = (V, A): 有向グラフ定義 φ :
A → R に対し，その境界 ∂φ : V → R を ∑ ∑ (∂φ)(i) := φ(a) − φ(a) a∈Out(i) (i ∈ V ) a∈In(i) と定義する．ここで，In(i), Out(i) はそれぞれ頂点 i に入る枝，出る枝の集合． ※ δ + (i), δ − (i) と表記する本もある． 8 / 36

最大流問題: 定義 G = (V, A): 有向グラフ, u : A
→ R+ : 枝容量関数 s, t ∈ V : 始点, 終点定義 (s–t 流) フロー def φ : A → R が s–t 流 ⇐⇒ • 0 ≤ φ(a) ≤ u(a) (a ∈ A) • (∂φ)(i) = 0 (i ∈ V \ {s, t}) （容量制約）（流量保存則） 9 / 36

最大流問題: 定義 G = (V, A): 有向グラフ, u : A
→ R+ : 枝容量関数 s, t ∈ V : 始点, 終点定義 (s–t 流) フロー def φ : A → R が s–t 流 ⇐⇒ • 0 ≤ φ(a) ≤ u(a) (a ∈ A) • (∂φ)(i) = 0 (i ∈ V \ {s, t}) （容量制約）（流量保存則）最大流問題 (Maximum Flow Problem) s–t 流 φ で流量 val(φ) := (∂φ)(s) = −(∂φ)(t) が最大のものを求めよ． 9 / 36

例 φ: 流量 / u: 容量 3/3 4/ 5 1/1
2/ /2 s 1 1/2 5/ t 3/ 3 5 3 3/4 流量: 7 （実は最大流） 10 / 36

最大流問題: 線形計画問題として主問題 (P) ∑ max φ(a) a∈Out(s) ∑ s.t.
∑ φ(a) − a∈Out(i) φ(a) = 0 (i ∈ V \ {s, t}) a∈In(i) 0 ≤ φ(a) ≤ u(a) (a ∈ A) 双対問題 (D) min ∑ u(a)y(a) a∈A s.t. x(j) + y(a) ≥ 1 (a = sj ∈ Out(s)) − x(i) + y(a) ≥ 0 (a = it ∈ In(t)) x(j) − x(i) + y(a) ≥ 0 (a = ij ∈ A \ Out(s) ∪ In(t)) y(a) ≥ 0 (a ∈ A) 11 / 36

最大流問題: 線形計画問題として主問題 (P) max ∑ φ(a) a∈Out(s) s.t. ∑
∑ φ(a) − φ(a) = 0 (i ∈ V \ {s, t}) a∈In(i) a∈Out(i) 0 ≤ φ(a) ≤ u(a) (a ∈ A) 双対問題 (D) min x∈RV s.t. ∑ u(a) max{x(i) − x(j), 0} a=ij∈A x(s) = 1 x(t) = 0 11 / 36

最大流問題: 整数性ネットワーク行列有向グラフ G = (V, A) に対し， V
× A 行列 B を   +1 (i は a の始点) Bi,a := −1 (i は a の終点)  0 otherwise (i ∈ V, a ∈ A) と定める． a b c d  +1 +1 0 −1 0 0  B= 0 0 +1 0 −1 −1  補題ネットワーク行列は完全単模行列． 12 / 36

最大流問題: 整数性 [ ] B̃ 最大流問題の係数行列は . ここで B̃ は
B から s と t の行を除いた I もの．ネットワーク行列の完全単模性より，この行列も完全単模．完全単模行列と LP の整数性（第 1 回参照）から，以下の定理が従う．定理最大流問題には整数双対最適解が存在する．さらに，枝容量 u が整数値のときは，整数値の最大流が存在する． 13 / 36

最大流最小カット定理 Out(X) 定義 def • X ⊆ V が s–t
カット ⇐⇒ s ∈ X, t ̸∈ X ∑ • s–t カット X の容量: u(Out(X)) = a∈Out(X) u(a) s t X 14 / 36

カット ⇐⇒ s ∈ X, t ̸∈ X ∑ • s–t カット X の容量: u(Out(X)) = a∈Out(X) u(a) s t X 弱双対性任意の s–t 流 φ と s–t カット X に対し，次が成り立つ． val(φ) ≤ u(Out(X)) 14 / 36

カット ⇐⇒ s ∈ X, t ̸∈ X ∑ • s–t カット X の容量: u(Out(X)) = a∈Out(X) u(a) s t X 弱双対性任意の s–t 流 φ と s–t カット X に対し，次が成り立つ． val(φ) ≤ u(Out(X)) 最大流最小カット定理 (Ford–Fulkerson, 1956; Danzig–Fulkerson, 1956) max val(φ) = φ : s –t 流 min X : s–t カット u(Out(X)) 次回，アルゴリズム的な証明を与える． 14 / 36

例 φ: 流量 / u: 容量 3/3 4/ 5 1/1
2/ /2 s 1 1/2 5/ t 3/ 3 5 3 3/4 流量: 7 （実は最大流） 15 / 36

実例: 冷戦時代 444 Alexander Schrijver 出典 Harris, T.E., Ross, F.S.
(1955): Fundamentals of a Method for Evaluating Rail Net Capacities. Research Memorandum Fig. 2. From Harris and Ross [11]: Schematic diagram of the railway network of the Western Soviet Union RM-1573, Thewith RAND Corporation, Santa Monica, and Eastern European countries, a maximum flow of value 163,000 tons fromCalifornia Russia to Eastern Europe, and a cut of capacity 163,000 tons indicated as “The bottleneck” 16 / 36

最大流を用いたモデリング最大流を用いたモデリングの例として以下を紹介する: 1 Menger の定理 (点素・辺素パス問題) 2 二部マッチング 3 Baseball
Elimination 4 最密部分グラフ問題 (密グラフ抽出) 18 / 36

辺素・点素パス問題有向 s–t 辺素パス問題入力: 有向グラフ G = (V, A),
s, t ∈ V 出力: 辺素 s–t パスの最大集合 s t 辺素 s–t パス 19 / 36

辺素・点素パス問題有向 s–t 辺素パス問題入力: 有向グラフ G = (V, A),
s, t ∈ V 出力: 辺素 s–t パスの最大集合 s t 辺素 s–t パス有向 s–t 点素パス問題入力: 有向グラフ G = (V, A), s, t ∈ V 出力: 点素 s–t パスの最大集合 s t 点素 s–t パス 19 / 36

Menger の定理（有向・辺素 ver） Menger の定理（有向・辺素 ver）辺素 s–t パスの最大本数 =
min{| Out(X)| : s ∈ X ⊆ V \ t} s t 辺素 s–t パスの本数 ≤ | Out(X)| は自明．最小 s–t カット (| Out(X)| = 2) 20 / 36

Menger の定理（有向・辺素 ver） Menger の定理（有向・辺素 ver）辺素 s–t パスの最大本数 =
min{| Out(X)| : s ∈ X ⊆ V \ t} s t 辺素 s–t パスの本数 ≤ | Out(X)| は自明．最小 s–t カット (| Out(X)| = 2) (証明) 枝容量 u ≡ 1 として s–t 最大流を考えると，整数の s–t 流は辺素 s–t パスに対応する．整数性より，整数の s–t 最大流が存在する． Menger の定理は最大流最小カット定理に他ならない． 20 / 36

Menger の定理（有向・点素 ver） Menger の定理（有向・点素 ver）点素 s–t パスの最大本数 =
min{|U | : U ⊆ V は s と t を分離 } 点素 s–t パスの本数 ≤ |U | は自明． s t 最小 s–t 分離集合 (|U | = 2) 21 / 36

Menger の定理（有向・点素 ver） Menger の定理（有向・点素 ver）点素 s–t パスの最大本数 =
min{|U | : U ⊆ V は s と t を分離 } s 点素 s–t パスの本数 ≤ |U | は自明． t 最小 s–t 分離集合 (|U | = 2) (証明) s, t 以外の各頂点を以下のように変換したネットワークで，最大流最小カット定理を適用すればよい． +∞ v −→ v1 1 +∞ v2 21 / 36

Menger の定理（無向・点素 ver） Menger の定理には無向グラフ版もある．無向 s–t 点素パス問題入力: 無向グラフ
G = (V, E), s, t ∈ V 出力: 点素 s–t パスの最大集合 s t 最小 s–t 分離集合 (|U | = 2) Menger の定理（無向・点素 ver）点素 s–t パスの最大本数 = min{|U | : U ⊆ V は s と t を分離 } (証明) 各枝を両方向に向きづけた有向グラフに対し，有向・点素 Menger を使う． 22 / 36

Menger の定理（無向・辺素 ver） Menger の定理（無向・辺素 ver）辺素 s–t パスの最大本数 =
min{|E[X, X̄]| : s ∈ X ⊆ V \ t} s t 最小 s–t カット (size = 3) (証明) 各枝を以下のように変換した有向グラフで，有向・辺素 Menger を適用すればよい． 1 i j −→ j i 2 23 / 36

Kőnig–Egerváry の定理（復習） G = (V + , V − ;
E) を V + , V − を頂点集合とする二部グラフとする．定義 S ⊆ V + , T ⊆ V − が頂点被覆 def ⇐⇒ 任意の枝 e = ij ∈ E に対し，i ∈ S または j ∈ T . S 定理 (Kőnig–Egerváry) 二部グラフ G において，次の最大最小定理が成り立つ． T max M : マッチング |M | = min (S, T ): 頂点被覆 |S| + |T | 25 / 36

最大流最小カット =⇒ Kőnig–Egerváry 26 / 36

最大流最小カット =⇒ Kőnig–Egerváry +∞ 1 1 1 1 s t
1 1 +∞ 26 / 36

1 1 +∞ 整数 s–t 流 ←→ マッチング 26 / 36

1 1 +∞ 整数 s–t 流 ←→ マッチング有限値の s–t カット X ←→ 頂点被覆 S = V + \ X, T = V − ∩ X X の容量 = |S| + |T | 26 / 36

Baseball Elimination 野球のリーグ優勝争いの例: チーム勝ち数残り試合数 NYY New York Yankees
(NYY) Boston Red Sox (BOS) Toronto Blue Jays (TOR) Baltimore Orioles (BAL) 93 89 88 86 8 4 7 5 残りの対戦予定 BOS TOR BAL – 1 6 1 1 – 0 3 6 0 – 1 1 3 1 – 出典: D.P. Williamson Network Flow Algorithms （簡単のため，試合結果に引き分けはないものとする）定義チーム k が脱落している (eliminated) def ⇐⇒ 任意の残り試合結果において，チーム k より勝ち数の多いチームが存在する 28 / 36

Baseball Elimination チーム勝ち数残り試合数 NYY New York Yankees (NYY)
Boston Red Sox (BOS) Toronto Blue Jays (TOR) Baltimore Orioles (BAL) 93 89 88 86 8 4 7 5 残りの対戦予定 BOS TOR BAL – 1 6 1 1 – 0 3 6 0 – 1 1 3 1 – 出典: D.P. Williamson Network Flow Algorithms • BAL は脱落している． ∵ BAL の現在の勝ち数 86 + 残り試合数 5 < NYY の現在の勝ち数 93 29 / 36

Baseball Elimination チーム勝ち数残り試合数 NYY New York Yankees (NYY)
Boston Red Sox (BOS) Toronto Blue Jays (TOR) Baltimore Orioles (BAL) 93 89 88 86 8 4 7 5 残りの対戦予定 BOS TOR BAL – 1 6 1 1 – 0 3 6 0 – 1 1 3 1 – 出典: D.P. Williamson Network Flow Algorithms • BAL は脱落している． ∵ BAL の現在の勝ち数 86 + 残り試合数 5 < NYY の現在の勝ち数 93 • BOS は脱落している． ∵ BOS が残り全勝すると， 89 + 4 = 93 勝. もし NYY が 1 勝でもすれば，BOS を上回る．一方，NYY が全敗したとすると，TOR が 88 + 6 = 94 勝で BOS を上回る． 29 / 36

Baseball Elimination Baseball Elimination 入力: チーム集合 T , 現在の勝ち数 w(i)
∈ Z+ (i ∈ T ), 残り試合数 g(i, j) ∈ Z+ (i, j ∈ T ) 出力: 特定のチーム k ∈ T が脱落しているか否か定理 Baseball Elimination は 1 回の最大流計算で解ける．記号 g(k) := ∑ i∈T g(k, i) ... チーム k の残り試合数 30 / 36

g(i, j): i, j の残り試合数最大流への帰着 g(k): k の残り試合数 w(i):
i の現在の勝ち数 k 以外のペア +∞ k 以外のチーム i w(k) + g(k) − w(i) g(i, j) s i, j t j 補題 w(k) + g(k) − w(i) ≥ 0 (i ∈ T \ k ) とする．このとき， s から出る全ての枝の容量を飽和する流が存在 ⇐⇒ k は脱落していない 31 / 36

最密部分グラフ問題最密部分グラフ問題入力無向グラフ G = (V, E), 枝重み w
: E → R+ 出力密度 w(E[S]) |S| が最大となる頂点部分集合 ∅ ̸= S ⊆ V 引用:『組合せ最適化から機械学習へ：劣モジュラ最適化とグラフマイニング』サイエンス社 33 / 36

最小カットへの帰着固定された γ ≥ 0 に対し， w(E[S]) > γ を満たす
S が存在するか？ (存在するなら求めよ) |S| を解ければよい．（γ に関して二分探索）つまり最小化問題 min [γ|S| − w(E[S])] < 0 S⊆V を解ければよい．方針この最小化問題を最小 s–t カットで表現する 34 / 36

最小カットへの帰着 d(v) := w(δ(v)) ... 重み付き次数 G の頂点 V v
w( ) .. . w (E ) i w( E s w(ij) w (E ) w( E ) E )+ 2γ − d( v) w(ij) t j .. . E w( )+ 2γ − d( u) u 35 / 36

組合せ最適化特論第 5 回（最大流②）担当: 相馬輔 2026/5/28 1 /
23

目次 1. Ford–Fulkerson 法・残余ネットワーク・最大流最小カット定理の証明・反復回数
2. Edmonds–Karp 法・ Edmonds–Karp 法・距離ラベルを用いた解析・まとめ 2 / 23

最大流問題（復習） G = (V, A): 有向グラフ定義 φ : A
→ R に対し，その境界 ∂φ : V → R を ∑ ∑ (∂φ)(i) := φ(a) − φ(a) a∈Out(i) (i ∈ V ) a∈In(i) と定義する．ここで，In(i), Out(i) はそれぞれ頂点 i に入る枝，出る枝の集合． ※ δ + (i), δ − (i) と表記する本もある． 4 / 23

最大流問題（復習） G = (V, A): 有向グラフ, u : A →
R+ : 枝容量関数 s, t ∈ V : 始点, 終点定義 (s–t 流) フロー def φ : A → R が s–t 流 ⇐⇒ • 0 ≤ φ(a) ≤ u(a) (a ∈ A) • (∂φ)(i) = 0 (i ∈ V \ {s, t}) （容量制約）（流量保存則） 5 / 23

最大流問題（復習） G = (V, A): 有向グラフ, u : A →
R+ : 枝容量関数 s, t ∈ V : 始点, 終点定義 (s–t 流) フロー def φ : A → R が s–t 流 ⇐⇒ • 0 ≤ φ(a) ≤ u(a) (a ∈ A) • (∂φ)(i) = 0 (i ∈ V \ {s, t}) （容量制約）（流量保存則）最大流問題 (Maximum Flow Problem) s–t 流 φ で流量 val(φ) := (∂φ)(s) = −(∂φ)(t) が最大のものを求めよ． 5 / 23

カット ⇐⇒ s ∈ X, t ̸∈ X ∑ • s–t カット X の容量: u(Out(X)) = a∈Out(X) u(a) s t X 6 / 23

カット ⇐⇒ s ∈ X, t ̸∈ X ∑ • s–t カット X の容量: u(Out(X)) = a∈Out(X) u(a) s t X 弱双対性任意の s–t 流 φ と s–t カット X に対し，次が成り立つ． val(φ) ≤ u(Out(X)) 6 / 23

カット ⇐⇒ s ∈ X, t ̸∈ X ∑ • s–t カット X の容量: u(Out(X)) = a∈Out(X) u(a) s t X 弱双対性任意の s–t 流 φ と s–t カット X に対し，次が成り立つ． val(φ) ≤ u(Out(X)) 最大流最小カット定理 (Ford–Fulkerson, 1956; Danzig–Fulkerson, 1956) max val(φ) = φ : s –t 流 min X : s–t カット u(Out(X)) 6 / 23

残余ネットワーク定義 (残余ネットワーク) • s–t 流 φ に対し，残余ネットワーク Gφ =
(V, Aφ ) を次のように定める: lo Aφ := Aup φ ∪ Aφ Aup φ := {a ∈ A : φ(a) < u(a)} . . . . . . . . . φ を増やせる枝 −1 Alo : a ∈ A, φ(a) > 0} φ := {a −1 ここで a は a の逆向き枝． . . . . . . . . . φ を減らせる枝 • 残余ネットワークの枝容量 cφ : Aφ → R+ を次のように定める: { u(a) − φ(a) (a ∈ Aup φ ) . . . . . . . . . φ を増減できる余裕量 cφ (a) := −1 φ(a ) (a ∈ Alo φ) 7 / 23

例 3/3 4/4 5 1 s 4 t 1 t
2 3 3/ 1 3 5 2 1/1 3 /2 2/ 0 s 4/ 5 2/2 5/ 2 3 4 元のネットワーク G φ: 流量 / u: 容量残余ネットワーク Gφ lo Aup φ , Aφ 8 / 23

増加道定義残余ネットワーク上の s–t パスを φ に対する増加道と呼ぶ．観察増加道があると，それに沿って流量を増やせる．残余ネットワーク
Gφ Aφup , Alo φ s s t +ε +ε 元のグラフ G −ε −ε +ε −ε +ε t 9 / 23

増加道に沿った流の更新増加道 P に対し，次の φ+ を考える:  up  φ(a)
+ ε (a ∈ P ∩ Aφ ) φ+ (a) := φ(a) − ε (a−1 ∈ P ∩ Alo φ)  φ(a) (otherwise) ここで ε = mina∈P cφ (a) である．このとき，φ+ は s–t 流であり，その流量は val(φ+ ) = val(φ) + ε． 10 / 23

増加道による最大流の特徴づけ補題 • s–t 流 φ が最大流 ⇐⇒ φ に対する増加道が存在しない．
• φ に対する増加道が存在しないとき，Gφ において s から到達可能な頂点集合 s ∈ X ⊆ V \ t は val(φ) = u(Out(X)) を満たす． cf. 弱双対性 val(φ) ≤ u(Out(X)) 最大二部マッチングの増加道による特徴づけ（第 2 回）の一般化 11 / 23

補題の証明増加道が存在しない =⇒ φ は最大流: X を残余ネットワーク Gφ において s
から到達可能な頂点集合とする．すると，Gφ において X から出る枝は存在しないことから，以下が成り立つ: • G において X から出る枝 a ∈ Out(X) に対し，φ(a) = u(a) • G において X に入る枝 a ∈ In(X) に対し，φ(a) = 0 よって， val(φ) = ∑ φ(a) − a∈Out(X) = ∑ ∑ φ(a) a∈In(X) u(a) − 0 = u(Out(X)). a∈Out(X) 弱双対が等号で成り立つので，φ は最大流． 12 / 23

Ford–Fulkerson 法補題から直ちに次のアルゴリズムが得られる． Ford–Fulkerson 法 1: φ ≡ 0. 2:
while 残余ネットワーク Gφ に増加道 P が存在 : ε ← min a∈P cφ (a) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . P に沿った最大の増加量 φ(a) + ε a ∈ P ∩ Aup φ  −1 4: φ(a) ← φ(a) − ε a ∈ P ∩ Alo φ  φ(a) otherwise 5: X := Gφ において s から到達可能な頂点集合 6: return φ, X 3: 定理 (Ford–Fulkerson, 1957) Ford–Fulkerson 法は停止した場合，最大流と最小カットを返す． 13 / 23

例 a d 元のネットワーク G φ: 流量 / u: 容量
c t s 2 5 5 3 0/ 3 5 1 0/4 0/ 2 b c 0/1 3 /2 0/ 0/3 0 s 5 0/2 0/ a 3 3 t 4 b d 残余ネットワーク Gφ lo Aup φ , Aφ 流量: 0 14 / 23

例 a 3 0/ d 元のネットワーク G φ: 流量 /
u: 容量 5 t s c 3 2 2 5 1 1 2/4 2/ 1 2 2 3 2 b c 0/1 3 /2 2/ 2/3 2 s 5 0/2 0/ a t 2 b 2 d 残余ネットワーク Gφ lo Aup φ , Aφ 流量: 2 14 / 23

例 a 元のネットワーク G φ: 流量 / u: 容量 t
2 1 s c 3 2 1 3 2/ d 3 5 1 2 2 b 4 t 1 2 4/4 2/ 2 b c 0/1 3 /2 2/ 2/3 2 s 5 2/2 2/ a d 2 残余ネットワーク Gφ lo Aup φ , Aφ 流量: 4 14 / 23

例 a 元のネットワーク G φ: 流量 / u: 容量 t
3 1 s c 2 3 1 3 2/ d 2 5 3 2 b 4 t 1 2 4/4 3/ 2 b c 0/1 3 /2 2/ 3/3 2 s 5 2/2 3/ a d 2 残余ネットワーク Gφ lo Aup φ , Aφ 流量: 5 14 / 23

例 a 4 1 s 1 元のネットワーク G φ: 流量
/ u: 容量 t c 2 3 3 t 1 3 3/ d 1 5 1 4/4 3/ 2 b c 0/1 3 /2 2/ 3/3 1 s 5 2/2 4/ a 2 b 4 d 3 残余ネットワーク Gφ lo Aup φ , Aφ 流量: 6 14 / 23

例 d c 1 3 t 5 1 s 4
t 1 3 3/ 元のネットワーク G φ: 流量 / u: 容量流量: 7 a 5 2 4/4 4/ 2 b c 1/1 3 /2 2/ 3/3 0 s 5 2/2 5/ a 2 b 4 d 3 残余ネットワーク Gφ lo Aup φ , Aφ 【終了】 14 / 23

Ford–Fulkerson 法残余ネットワークの構築・増加道の探索・流の更新: O(m) 時間 (m = |A|) 反復回数 •
枝容量が整数値のとき: 各反復で流量が少なくとも 1 増加．したがって，最大流量を F とすると，高々 F 回の反復． −→ 全体では O(mF ) 時間（擬多項式時間） • 枝容量が無理数値のとき: 増加道の選び方によっては，有限回で停止せず，かつ最大でない流に収束してしまう例がある [Ford–Fulkerson, 1962] 15 / 23

Edmonds–Karp 法 Ford–Fulkerson 法において，枝数が最小の増加道を選ぶ．（たとえば，幅優先探索で s–t パスを探索すればよい）定理 (Edmonds–Karp, 1972)
任意の枝容量に対し，Edmonds–Karp 法は O(mn) 回の反復で終了する．したがって，O(m2 n) 時間で最大流と最小カットを求められる．強多項式時間 (n = |V |, m = |A|) 17 / 23

Edmonds–Karp 法の解析 φ: Edmonds–Karp 法の途中の流 P : 選ばれた φ 増加道
φ+ : P に沿って更新した流補題 (距離ラベルの単調性) d(i) := Gφ における頂点 i から t までの最短距離（枝数） d+ (i) := Gφ+ における頂点 i から t までの最短距離（枝数）とする．このとき，任意の頂点 i ∈ V に対し，d(i) ≤ d+ (i) が成り立つ． 18 / 23

Edmonds–Karp 法の解析 (証明) 背理法．d(i) > d+ (i) となる頂点 i が存在すると仮定する．そ
のような頂点 i の中で d+ (i) が最小のものを取る（最小反例）． d(t) = d+ (t) = 0 より i ̸= t. 19 / 23

のような頂点 i の中で d+ (i) が最小のものを取る（最小反例）． d(t) = d+ (t) = 0 より i ̸= t. j := Gφ+ の i から t への最短路における i の直後の頂点とする．このとき，次が成立: • d(j) ≤ d+ (j) (i の最小性から) + + • d (i) = d (j) + 1 (j の定義から) 19 / 23

のような頂点 i の中で d+ (i) が最小のものを取る（最小反例）． d(t) = d+ (t) = 0 より i ̸= t. j := Gφ+ の i から t への最短路における i の直後の頂点とする．このとき，次が成立: • d(j) ≤ d+ (j) (i の最小性から) + + • d (i) = d (j) + 1 (j の定義から) Claim. ij ∈ / Aφ (∵) もし ij ∈ Aφ ならば， d(i) ≤ d(j) + 1 ≤ d+ (j) + 1 = d+ (i) となり，そもそもの仮定 d(i) > d+ (i) に矛盾． 19 / 23

Edmonds–Karp 法の解析 Claim. ij ∈ / Aφ したがって， • 更新前の
Gφ には ji が存在し，その逆向き枝 ij は存在しない． • 一方，更新後の Gφ+ に ij が現れているので，ji は Gφ の最短路 P に含まれていたことになる． ∴ d(j) = d(i) + 1 . すると， d(i) = d(j) − 1 ≤ d+ (j) − 1 = d+ (i) − 2 (上式を移項) (d(j) ≤ d+ (j)) (d+ (i) = d+ (j) + 1) となり，そもそもの仮定 d(i) > d+ (i) に矛盾． 20 / 23

Edmonds–Karp 法の解析定理 (Edmonds–Karp) 任意の枝容量に対し，Edmonds–Karp 法は O(mn) 回の反復で終了する．したがって，O(m2 n)
時間で最大流と最小カットを求められる． (証明) ij ∈ Aφ が，更新後に ij ∈ / Aφ+ となったとき，ij は飽和したという． • 各反復では，P の少なくとも 1 本の枝が飽和する．飽和した枝 ij について d(i) = d(j) + 1 が成り立つ． 21 / 23

時間で最大流と最小カットを求められる． (証明) ij ∈ Aφ が，更新後に ij ∈ / Aφ+ となったとき，ij は飽和したという． • 各反復では，P の少なくとも 1 本の枝が飽和する．飽和した枝 ij について d(i) = d(j) + 1 が成り立つ． • 一度飽和した ij が再び飽和するには，その間に ji が一度は最短路に含まれる必要がある．そのときの距離ラベルに関して，d(j) = d(i) + 1 が成り立つ． 21 / 23

時間で最大流と最小カットを求められる． (証明) ij ∈ Aφ が，更新後に ij ∈ / Aφ+ となったとき，ij は飽和したという． • 各反復では，P の少なくとも 1 本の枝が飽和する．飽和した枝 ij について d(i) = d(j) + 1 が成り立つ． • 一度飽和した ij が再び飽和するには，その間に ji が一度は最短路に含まれる必要がある．そのときの距離ラベルに関して，d(j) = d(i) + 1 が成り立つ． • 距離ラベル d(i) ≤ n or d(i) = +∞ (i から t へ到達不能の場合) 21 / 23

時間で最大流と最小カットを求められる． (証明) ij ∈ Aφ が，更新後に ij ∈ / Aφ+ となったとき，ij は飽和したという． • 各反復では，P の少なくとも 1 本の枝が飽和する．飽和した枝 ij について d(i) = d(j) + 1 が成り立つ． • 一度飽和した ij が再び飽和するには，その間に ji が一度は最短路に含まれる必要がある．そのときの距離ラベルに関して，d(j) = d(i) + 1 が成り立つ． • 距離ラベル d(i) ≤ n or d(i) = +∞ (i から t へ到達不能の場合) よって，距離ラベルの単調性と合わせると，各枝は高々 n/2 回飽和しうる．ゆえに全体の反復は O(mn) 回． 21 / 23

Edmonds–Karp 法の解析 n d′′ (i) d′ (j) d′′ (j) d′
(i) d(i) d(j) 0 ij が飽和したとき d(i) = d(j) + 1 ji が最短路に含まれたとき ij が再度飽和したとき d′ (j) = d′ (i) + 1 d′′ (i) = d′′ (j) + 1 22 / 23

まとめ最大流問題 • 最大流最小カット定理，整数性 • Ford–Fulkerson 法: 枝容量が整数値のとき O(mF )
時間 • Edmonds–Karp 法: O(m2 n) 時間その他の最大流アルゴリズム • Dinitz (1970): O(mn2 ) 時間動的木を用いると O(mn log n) 時間 (Sleator–Tarjan, 1983) √ • プッシュ・再ラベル (Goldberg–Tarjan, 1988): O(n2 m) 時間動的木を用いると O(mn log(n2 /m)) 時間 23 / 23

組合せ最適化特論第 6 回（最小費用流）担当: 相馬輔 2026/6/11 1 /
47

目次 1. 最小費用流問題・定式化・ Hitchcock 型輸送問題・ Gale
の定理・負閉路最適性条件 2. アルゴリズム・逐次最短路法，主双対法・容量スケーリング・まとめ 6 / 47

境界 G = (V, A): 有向グラフ定義 φ : A
→ R に対し，その境界 ∂φ : V → R を ∑ ∑ (∂φ)(i) := φ(a) − φ(a) a∈Out(i) (i ∈ V ) a∈In(i) と定義する．ここで，In(i), Out(i) はそれぞれ頂点 i に入る枝，出る枝の集合． ※ δ + (i), δ − (i) と表記する本もある． 8 / 47

b流 G = (V, A): 有向グラフ, u : A →
R+ : 枝容量関数, b : V → R with b(V ) = 0 定義 (b 流) def φ : A → R が（実行可能）b 流 ⇐⇒ • 0 ≤ φ(a) ≤ u(a) (a ∈ A) • (∂φ)(i) = b(i) (i ∈ V ) （容量制約）（境界条件）解釈 • b(i) > 0: 供給点，湧き出し口 • b(i) = 0: 流量保存する頂点 • b(i) < 0: 需要点，吸い込み口特に，b ≡ 0 のとき，φ は循環流 (circulation) と呼ばれる． 9 / 47

例 φ: 流量 / u: 容量頂点の数字: b 0 4/
1/1 /2 2/ 1 +7 0 5 1/2 5/ 3/3 3 5 3 1/ −5 3/4 0 −2 10 / 47

最小費用流問題 • G = (V, A): 有向グラフ • u :
A → R+ : 枝容量関数 • b : V → R with b(V ) = 0 • c : A → R: 枝費用関数最小費用流問題 (Minimum Cost Flow Problem) ∑ b 流 φ で費用 c(φ) := a∈A c(a)φ(a) が最小のものを求めよ．（もしくは，b 流が存在しないことを示せ） 11 / 47

最小費用流: 線形計画問題として最小費用流の方が LP として美しい形になる．主問題 (P) min s.t. c⊤
φ ∑ ∑ φ(a) − a∈Out(i) φ(a) = b(i) (i ∈ V ) a∈In(i) 0 ≤ φ(a) ≤ u(a) (a ∈ A) 双対問題 (D) max ∑ b(i)x(i) − ∑ u(a)y(a) x∈RV ,y∈RA + i∈V s.t. x(i) − x(j) − y(a) ≤ c(a) (a = ij ∈ A) y(a) ≥ 0 (a ∈ A) a∈A 12 / 47

最小費用流の整数性主問題 (P) の係数行列は G のネットワーク行列であり，したがって完全単模行列である．完全単模行列と LP の整数性（第
1 回参照）から，以下の定理が従う．定理枝容量 u と境界 b がともに整数値だとする．このとき，最小費用流問題が実行可能であれば，整数値の最小費用流が存在する． 13 / 47

最大流 ⊂ 最小費用流 s–t 最大流は最小費用流問題の特殊ケース． G に枝 a∗ = ts
を追加した有向グラフを G′ とし，その上の循環流を考える． s 容量 { u′ (a) := 枝費用 { c(a) := +∞ (a = a∗ ) u(a) (a ∈ A) t a∗ −1 (a = a∗ ) 0 (otherwise) とすればよい． 14 / 47

最短路問題 ⊂ 最小費用流最短路問題は最小費用流問題の特殊ケース． • 容量: u ≡ +∞ 
 +1 (i = s) • 境界: b(i) = −1 (i = t)  0 (otherwise) −1 s t +1 • 費用 c = ℓ (最短路問題の枝長) 15 / 47

Hitchcock 型輸送問題 G = (V + , V − ;
E): 二部グラフ b+ : V + → R+ : 供給関数, b− : V − → R+ : 需要関数 with b+ (V + ) = b− (V − ) c : E → R: 枝費用関数 V + 輸送 p(i, j) V − Hitchcock 型輸送問題 min ∑ 供給 b+ (i) c(i, j)p(i, j) 需要 b− (j) (i,j)∈E s.t. ∑ p(i, j) = b+ (i) (i ∈ V + ) j∈Γ(i) ∑ p(i, j) = b− (j) (j ∈ V − ) i∈Γ(j) p(i, j) ≥ 0 ((i, j) ∈ E) 16 / 47

輸送問題と最小費用流補題 n 頂点, m 枝の最小費用流問題は，n + m 頂点, 2m
枝の Hitchcock 型輸送問題に帰着できる． (証明) G′ = (V + , V − ; E), b+ , b− , c を次のように構成する: • V + := A, V − := V ∪ • E = a=ij∈A {(a, i), (a, j)} A V u(a) u(Out(j)) − b(j) • b+ (a) := u(a) (a ∈ V + ) b− (i) := u(Out(i)) − b(i) (i ∈ V − ) • c(a, i) := 0, c(a, j) := c(a) (a = ij ∈ A) ∑ b+ (V + ) = u(A) = i∈V (u(Out(i)) − b(i)) = b− (V − ) より，これは Hitchcock 型輸送問題を定める． 17 / 47

輸送問題と最小費用流 (G, u) 上の b 流 φ に対し， p(a, i)
:= u(a) − φ(a) p(a, j) := φ(a) A V u(a) − φ(a) u(a) φ( a) u(Out(i)) − b(i) (a = ij ∈ A) と定めると，p は輸送問題の実行可能解であり，c′ (p) = c(φ). 逆に，輸送問題の実行可能解 p に対し， φ(a) := p(a, j) (a = ij ∈ A) と定めると，φ は (G, u) 上の b 流であり，c(φ) = c′ (p). 18 / 47

実行可能性: Gale の定理定理（もし存在するならば）b 流は 1 回の最大流問題で求められる． (証明) 右図のグラフ
G′ = (V ′ , A′ ) と枝容量を考える:   u(a) (a ∈ A) ′ u (a) = b(i) (a = si, b(i) > 0)  −b(i) (a = it, b(i) < 0) (G′ , u′ ) の流量 b(V + ) の s–t 流 ←→ (G, u) の b 流 19 / 47

実行可能性: Gale の定理定理（もし存在するならば）b 流は 1 回の最大流問題で求められる． (証明) 右図のグラフ
G′ = (V ′ , A′ ) と枝容量を考える:   u(a) (a ∈ A) ′ u (a) = b(i) (a = si, b(i) > 0)  −b(i) (a = it, b(i) < 0) (G′ , u′ ) の流量 b(V + ) の s–t 流 ←→ (G, u) の b 流系 (Gale, 1957) b 流が存在 ⇐⇒ b(X) ≤ u(OutG (X)) (X ⊆ V ) (証明) (G′ の s–t カット容量) ≥ b(V + ) を書き換える． 19 / 47

残余ネットワーク b 流に関しても残余ネットワークの定義は同じ．定義 (残余ネットワーク) • b 流 φ に対し，残余ネットワーク
Gφ = (V, Aφ ) を次のように定める: lo Aφ := Aup φ ∪ Aφ Aup φ := {a ∈ A : φ(a) < u(a)} . . . . . . . . . φ を増やせる枝 −1 Alo : a ∈ A, φ(a) > 0} φ := {a −1 ここで a は a の逆向き枝． . . . . . . . . . φ を減らせる枝 • 残余ネットワークの枝容量 cφ : Aφ → R+ を次のように定める: { u(a) − φ(a) (a ∈ Aup φ ) cφ (a) := . . . . . . . . . φ を増減できる余裕量 −1 φ(a ) (a ∈ Alo φ) 20 / 47

残余ネットワークを用いた流の更新 φ: b 流残余ネットワーク Gφ 上のパス or 閉路 Q
に沿って流を更新する:  up  φ(a) + ε (a ∈ Q ∩ Aφ ) φ+ (a) := φ(a) − ε (a−1 ∈ Q ∩ Alo φ)  φ(a) (otherwise) ここで，ε ≤ mina∈Q cφ (a). 21 / 47

残余ネットワークを用いた流の更新 φ: b 流残余ネットワーク Gφ 上のパス or 閉路 Q
に沿って流を更新する:  up  φ(a) + ε (a ∈ Q ∩ Aφ ) φ+ (a) := φ(a) − ε (a−1 ∈ Q ∩ Alo φ)  φ(a) (otherwise) ここで，ε ≤ mina∈Q cφ (a). 観察 • Q が s–t パスならば，φ+ は b′ = b + ε(es − et ) に関する b′ 流． • Q が閉路ならば，φ+ は b 流． 21 / 47

残余ネットワークさらに残余ネットワークの枝長 ℓφ : Aφ → R を次のように定める: { c(a)
(a ∈ Aup φ ) ℓφ (a) := −1 −c(a ) (a ∈ Alo φ) 観察 Q に沿った流の更新により，費用は次のように変化する: c(φ+ ) = c(φ) + εℓφ (Q) 22 / 47

残余ネットワークさらに残余ネットワークの枝長 ℓφ : Aφ → R を次のように定める: { c(a)
(a ∈ Aup φ ) ℓφ (a) := −1 −c(a ) (a ∈ Alo φ) 観察 Q に沿った流の更新により，費用は次のように変化する: c(φ+ ) = c(φ) + εℓφ (Q) (復習) p : V → R が枝長 ℓ : A → R に関するポテンシャル def ⇐⇒ p(j) − p(i) ≤ ℓ(a) (a = ij ∈ A) 22 / 47

負閉路最適性条件定理 (Klein (1967), Ford–Fulkerson (1962)) b 流 φ に対し，次の
3 条件は同値: 1 φ は最小費用流 2 残余ネットワーク Gφ に（ℓφ に関する）負閉路が存在しない 3 残余ネットワーク Gφ に（ℓφ に関する）ポテンシャルが存在最小重み完全マッチングの最適性条件（第 3 回）の一般化． 23 / 47

負閉路最適性条件定理 (Klein (1967), Ford–Fulkerson (1962)) b 流 φ に対し，次の
3 条件は同値: 1 φ は最小費用流 2 残余ネットワーク Gφ に（ℓφ に関する）負閉路が存在しない 3 残余ネットワーク Gφ に（ℓφ に関する）ポテンシャルが存在最小重み完全マッチングの最適性条件（第 3 回）の一般化． (証明) ① =⇒ ②: 負閉路 C に沿って φ を更新すると，φ+ は b 流で， c(φ+ ) = c(φ) + εℓφ (C) < c(φ) となり矛盾． ② ⇐⇒ ③: 最短路問題（第 3 回）でやった ③ =⇒ ①: LP の相補性条件から従う（次スライド） 23 / 47

φ ∑ ∑ φ(a) − a∈Out(i) φ(a) = b(i) (i ∈ V ) a∈In(i) 0 ≤ φ(a) ≤ u(a) (a ∈ A) 双対問題 (D) max ∑ b(i)x(i) − ∑ u(a)y(a) x∈RV ,y∈RA + i∈V s.t. x(i) − x(j) − y(a) ≤ c(a) (a = ij ∈ A) y(a) ≥ 0 (a ∈ A) a∈A 24 / 47

φ ∑ ∑ φ(a) − a∈Out(i) φ(a) = b(i) (i ∈ V ) a∈In(i) 0 ≤ φ(a) ≤ u(a) (a ∈ A) （後の都合のため）x の符号を反転すると．．．双対問題 (D) max x∈RV ,y∈RA + s.t. − ∑ b(i)x(i) − i∈V ∑ u(a)y(a) a∈A − x(i) + x(j) − y(a) ≤ c(a) (a = ij ∈ A) y(a) ≥ 0 (a ∈ A) 24 / 47

相補性条件 Gφ のポテンシャル x : V → R に対し，y :
A → R を次のように定める． { −c(a) + x(j) − x(i) (φ(a) > 0)・・・a−1 に対するポテンシャル条件のスラック y(a) := 0 (otherwise) Claim (x, y) は双対実行可能解． 25 / 47

相補性条件 Gφ のポテンシャル x : V → R に対し，y :
A → R を次のように定める． { −c(a) + x(j) − x(i) (φ(a) > 0)・・・a−1 に対するポテンシャル条件のスラック y(a) := 0 (otherwise) Claim (x, y) は双対実行可能解． (∵) y ≥ 0: φ(a) > 0 のとき，a−1 が Gφ に存在するので，ポテンシャルの定義より x(i) − x(j) ≤ ℓφ (a−1 ) = −c(a). よって，y(a) ≥ 0. x(j) − x(i) − y(a) ≤ c(a): φ(a) > 0 のときは，y の定義から自明に制約を満たす．φ(a) = 0 のときは，a が Gφ に存在するので，ポテンシャルの定義より x(j) − x(i) ≤ ℓφ (a) = c(a) y(a) = 0 より，制約を満たす． 25 / 47

相補性条件 { y(a) := −c(a) + x(j) − x(i) (φ(a)
> 0) 0 (otherwise) Claim φ と (x, y) は相補性条件を満たす: φ(a)(c(a) + x(i) − x(j) + y(a)) = 0 (a = ij ∈ A) (u(a) − φ(a))y(a) = 0 (a ∈ A) すなわち，φ は最小費用流． 26 / 47

{ 相補性条件 y(a) := −c(a) + x(j) − x(i) (φ(a)
> 0) 0 (otherwise) Claim φ と (x, y) は相補性条件を満たす: φ(a)(c(a) + x(i) − x(j) + y(a)) = 0 (a = ij ∈ A) (u(a) − φ(a))y(a) = 0 (a ∈ A) すなわち，φ は最小費用流． (∵) 相補性条件の 1 つ目は y の定義より自明なので，2 つ目を示す．背理法．φ(a) < u(a) かつ y(a) > 0 と仮定する．このとき，y の定義から φ(a) > 0 である．よって， a と a−1 の両方が Gφ に存在するので，ポテンシャル条件より次が成立: x(j) − x(i) ≤ ℓφ (a) = c(a) x(i) − x(j) ≤ ℓφ (a−1 ) = −c(a). ∴ x(j) − x(i) = c(a). ところが，これを y の定義に代入すると，y(a) = 0 となってしまい矛盾． 26 / 47

アルゴリズム以下のアルゴリズムを紹介する: • 逐次最短路法 . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 重み付き二部マッチングの自然な拡張 • 主双対法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 重み付き二部マッチングの自然な拡張 • 容量スケーリング . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . NEW! cf. 最小重み二部マッチングに対する逐次最短路法・主双対法（第 3 回）仮定 • 境界 b, 枝容量 u は整数値 • 費用 c は非負例えば，Hitchcock 型輸送問題に帰着した後，費用 c′ := c + M 1 (M : 十分大) を考えればよい． 28 / 47

逐次最短路法記号流 φ に対し， U + = {i ∈
V : b(i) > (∂φ)(i)} − U = {i ∈ V : b(i) < (∂φ)(i)} . . . . . . 供給が余っている頂点 . . . . . . 需要が満たされていない頂点逐次最短路法 1: φ ← 0 2: while ∂φ ̸= b : 3: if 残余ネットワーク Gφ 上で U + から U − へ到達可能 : 4: 枝長 ℓφ に関する Gφ 上の U + –U − 最短路 P を求める // 初期流 // Bellman–Ford 法で O(mn) 時間 ε := min{mina∈P cφ (a), b(s) − ∂φ(s), ∂φ(t) − b(t)} (s, t: P の始点・終点) 5: 6: P に沿って φ を ε だけ更新する． 7: else: 8: return "b 流は存在しない" 9: return φ 29 / 47

逐次最短路法の証明次の 2 つの補題を示す．補題逐次最短路法で求まる流を 0 = φ0 ,
φ1 , · · · , φµ とする．このとき，各 k = 0, 1, . . . , µ に対し，φk は最小費用 b′ 流である（ここで，b′ = ∂φk ）．補題逐次最短路法の途中で，U + , U − ̸= ∅ かつ Gφ で U + から U − へ到達不能になったとする．このとき，(G, u) に b 流は存在しない． 30 / 47

逐次最短路法の証明補題逐次最短路法で求まる流を 0 = φ0 , φ1 , ·
· · , φµ とする．このとき，各 k = 0, 1, . . . , µ に対し，φk は最小費用 b′ 流である（ここで，b′ = ∂φk ）． (証明) k に関する帰納法．k = 0 のときは，c が非負かつ φ0 = 0 より，自明に最小費用 0 流． φ を最小費用 b′ 流とし，Gφ で U + から U − へ到達可能とする． Claim. (Gφ , ℓφ ) は U + –U − 最短路をもつ 31 / 47

· · , φµ とする．このとき，各 k = 0, 1, . . . , µ に対し，φk は最小費用 b′ 流である（ここで，b′ = ∂φk ）． (証明) k に関する帰納法．k = 0 のときは，c が非負かつ φ0 = 0 より，自明に最小費用 0 流． φ を最小費用 b′ 流とし，Gφ で U + から U − へ到達可能とする． Claim. (Gφ , ℓφ ) は U + –U − 最短路をもつ (∵) 負閉路最適性条件より，(Gφ , ℓφ ) には負閉路が存在しない． 31 / 47

· · , φµ とする．このとき，各 k = 0, 1, . . . , µ に対し，φk は最小費用 b′ 流である（ここで，b′ = ∂φk ）． (証明) k に関する帰納法．k = 0 のときは，c が非負かつ φ0 = 0 より，自明に最小費用 0 流． φ を最小費用 b′ 流とし，Gφ で U + から U − へ到達可能とする． Claim. (Gφ , ℓφ ) は U + –U − 最短路をもつ P を U + –U − 最短路とし，φ+ を更新後の b′′ 流とする． Claim. φ+ は最小費用 b′′ 流． 31 / 47

逐次最短路法の証明 Claim. φ+ は最小費用 b′′ 流． (∵) 負閉路最適性条件より，Gφ+ に負閉路は存在しないことを示せば良い． Gφ+
に負閉路 C が存在したと仮定．更新前の Gφ には負閉路 C はなかったので，C の逆向き枝が更新時の最短路 P に含まれていたことになる（下図）． P Gφ C すると，迂回路 P ′ で P より長さが短いものが存在し，矛盾． (注) 次に紹介する主双対法の証明では，(Gφ , ℓφ ) にポテンシャルの存在が示される．「̸ ∃ 負閉路 ⇐⇒ ∃ ポテンシャル」より，ここで証明したことの別証明を与えている． 32 / 47

逐次最短路法の証明補題逐次最短路法の途中で，U + , U − ̸= ∅ かつ
Gφ で U + から U − へ到達不能になったとする．このとき，(G, u) に b 流は存在しない． (証明) X ⊆ V を Gφ において U + から到達可能な頂点全体とする．定義から U + ⊆ X ⊆ V \ U −. Gφ において X から出る枝は存在しないことから，以下が成り立つ: • G において X から出る枝 a ∈ Out(X) に対し，φ(a) = u(a) • G において X に入る枝 a ∈ In(X) に対し，φ(a) = 0 33 / 47

逐次最短路法の証明また，U + , U − の定義から，以下が成り立つ: • ∂φ(i) <
b(i) (i ∈ U + ) • ∂φ(i) ≤ b(i) (i ∈ V \ U − ) 34 / 47

逐次最短路法の証明また，U + , U − の定義から，以下が成り立つ: • ∂φ(i) <
b(i) (i ∈ U + ) • ∂φ(i) ≤ b(i) (i ∈ V \ U − ) よって b(X) = b(U + ) + b(X \ U + ) > (∂φ)(U + ) + (∂φ)(X \ U + ) = (∂φ)(X) = φ(OutG (X)) − φ(InG (X)) = u(OutG (X)) − 0 (上の不等式) (X から出る枝がないことから) となり，Gale の定理より b 流は存在しない． 34 / 47

逐次最短路法の計算量計算量解析 • 整数性より，φ の更新は高々 B 回 (B := 12
∑ i∈V |b(i)| ... 総供給/総需要量) • 各更新は 1 回の (Gφ , ℓφ ) 上の最短路問題 −→ Bellman–Ford 法で O(mn) 時間 (n = |V |, m = |A|) 定理 (伊理 (1960)) 逐次最短路法は，O(mnB) 時間で，最小費用 b 流を求めるか，b 流が存在しないことを判定する．擬多項式時間 35 / 47

主双対法流 φ と (Gφ , ℓφ ) のポテンシャル p
の両方を保持することで，逐次最短路法の計算量を改善できる．定義 (簡約枝長 (復習)) 枝長 ℓ : A → R のポテンシャル p : V → R に関する簡約枝長 ℓp : A → R を次のように定める: ℓp (a) := ℓ(a) + p(i) − p(j) (a = ij ∈ A) 観察 • 任意の s–t 路 P に対し， ℓp (P ) = ℓ(P ) + p(s) − p(t). 特に，ℓp に関する s–t 最短路 ⇐⇒ ℓ に関する s–t 最短路． • ℓp ≥ 0 . . . . . . . . . . . . . . . . . . . . . . . Bellman-Ford 法ではなく Dijkstra 法が使える！ 37 / 47

主双対法主双対法 1: φ ← 0 // 初期流 2: p
← (G, c) のポテンシャル // 初期ポテンシャル．Dijkstra 法で O(m + n log n) 時間 3: while U + , U − ̸= ∅ : 4: if 残余ネットワーク Gφ で U + から U − へ到達可能 : 5: 簡約枝長 ℓφ,p に関する Gφ 上の U + –U − 最短路 P と最短路長関数 d を求める // Dijkstra 法で O(m + n log n) 時間 6: ε := min{mina∈P cφ (a), b(s) − ∂φ(s), ∂φ(t) − b(t)} (s, t: P の始点・終点) 7: P に沿って φ を ε だけ更新し，ポテンシャルを p ← p + d と更新する． 8: else: 9: return "b 流は存在しない" 10: return φ 38 / 47

主双対法の証明次の補題を示せば，あとは逐次最短路法の定理から従う．補題主双対法における p は，常に (Gφ , ℓφ )
上のポテンシャル． 39 / 47

上のポテンシャル． (証明) p+ := p + d とする．(d : V → R ... (Gφ , ℓφ,p ) 上の（U + からの）最短路長関数) Claim. p+ は (Gφ , ℓφ ) のポテンシャル． (∵) d は (Gφ , ℓφ,p ) のポテンシャルなので，任意の枝 a = ij ∈ Aφ に対し， d(j) − d(i) ≤ ℓφ,p (a) = ℓφ (a) + p(i) − p(j) が成り立つ．移項すると p+ (j) − p+ (i) ≤ ℓφ (a). 39 / 47

上のポテンシャル． (証明) p+ := p + d とする．(d : V → R ... (Gφ , ℓφ,p ) 上の（U + からの）最短路長関数) Claim. p+ は (Gφ , ℓφ ) のポテンシャル． (∵) d は (Gφ , ℓφ,p ) のポテンシャルなので，任意の枝 a = ij ∈ Aφ に対し， d(j) − d(i) ≤ ℓφ,p (a) = ℓφ (a) + p(i) − p(j) が成り立つ．移項すると p+ (j) − p+ (i) ≤ ℓφ (a). Claim. 更新後の流 φ+ に対し，p+ は (Gφ+ , ℓφ+ ) のポテンシャル． (∵) 最短路 P 上の枝 a = ij では，上の不等式で等号が成立: d(j) − d(i) = ℓφ,p (a) ⇐⇒ p+ (j) − p+ (i) = ℓφ (a) よって，φ の更新により P 上に逆向き枝が生じても，p+ がポテンシャルであることは保たれる． 39 / 47

主双対法の計算量計算量解析 • 整数性より，φ の更新は高々 B 回 (B := 12
∑ i∈V |b(i)| ... 総供給/総需要量) • 各更新は 1 回の (Gφ , ℓφ,p ) 上の最短路問題 −→ Dijkstra 法で O(m + n log n) 時間 (n = |V |, m = |A|) 定理 (Edmonds–Karp (1970), 冨澤 (1971)) 主双対法は，O((m + n log n)B) 時間で，最小費用 b 流を求めるか，b 流が存在しないことを判定する．擬多項式時間 40 / 47

容量スケーリング法逐次最短路法・主双対法の反復回数を O(B) → O(n log bmax ) に改善したもの． B
= 21 ∑ i∈V |b(i)|, bmax = maxi∈V |b(i)| 弱多項式時間追加の仮定 u ≡ +∞ （例えば，Hitchcock 型輸送問題に帰着すればよい）記号 • ∆ ∈ Z++ : スケーリングパラメータ • 流 φ に対し， U∆+ := {i ∈ U + : b(i) ≥ (∂φ)(i) +∆ } ⊆ U + U∆− := {i ∈ U − : b(i) ≤ (∂φ)(i) −∆ } ⊆ U − . . . . . . . . . . . . . . . . . . . . . . . ∆ 以上供給が余っている/需要が満たされていない頂点 φ が整数流の場合: ∆ = 1 =⇒ (U∆+ , U∆− ) = (U + , U − ). 42 / 47

容量スケーリング法 1: φ ← 0 // 初期流 2: p ←
(G, c) のポテンシャル // 初期ポテンシャル．Dijkstra 法で O(m + n log n) 時間 3: ∆ ← 2⌈log2 bmax ⌉ // 初期スケーリングパラメータ 4: while ∆ ≥ 1 : − + 5: if 残余ネットワーク Gφ で U∆ から U∆ へ到達可能 : − + 簡約枝長 ℓφ,p に関する Gφ 上の U∆ –U∆ 最短路 P と最短路長関数 d を求める // Dijkstra 法で O(m + n log n) 時間 7: P に沿って φ を ∆ だけ更新し，ポテンシャルを p ← p + d と更新する． 8: else: 9: ∆ ← ∆/2 // スケーリングパラメータの更新 10: if ∂φ = b : 11: return φ 12: else: 13: return "b 流は存在しない" 6: 43 / 47

容量スケーリング法の解析 ∆ が一定の間を ∆ フェーズと呼ぶ．観察 • ∆ フェーズにおける流 φ(a)
は ∆ の倍数． (∵) 初期流は φ ≡ 0 より自明．∆ フェーズにおける更新では，毎回 ∆ だけ増減するので OK．最後に，∆ → ∆/2 フェーズに移行したときも，φ が ∆ の倍数なので，自明に ∆/2 の倍数でもあるので OK． • 流 φ は容量制約 0 ≤ φ ≤ u を満たす． (∵) u ≡ +∞ より上限は自明．φ(a) > 0 のとき，φ(a) は ∆ の倍数なので，更新で ∆ だけ減らしても負にはならない． 44 / 47

容量スケーリング法の解析補題各 ∆ フェーズにおける更新は高々 n 回． (証明) φ: ∆
フェーズの開始時の流 + X : Gφ において U2∆ から到達可能な頂点全体とする．このとき， − + • U2∆ ⊆ X ⊆ V \ U2∆ . • u ≡ +∞ より，G に X から出る枝は存在しない． U∆+ − U2∆ + U2∆ U∆− X 45 / 47

フェーズの開始時の流 + X : Gφ において U2∆ から到達可能な頂点全体とする．このとき， − + • U2∆ ⊆ X ⊆ V \ U2∆ . • u ≡ +∞ より，G に X から出る枝は存在しない． − U2∆ U∆+ P + sℓU2∆ tℓ U∆− X (s1 , t1 ), . . . , (sk , tk ): ∆ フェーズ中の更新で使われた P の始点・終点（重複を許す） Claim |{ℓ : sℓ ∈ X, tℓ ∈ / X}| ≤ |{ℓ : sℓ ∈ / X, tℓ ∈ X}| 45 / 47

フェーズの開始時の流 + X : Gφ において U2∆ から到達可能な頂点全体とする．このとき， − + • U2∆ ⊆ X ⊆ V \ U2∆ . • u ≡ +∞ より，G に X から出る枝は存在しない． − U2∆ U∆+ P + sℓU2∆ tℓ U∆− X (s1 , t1 ), . . . , (sk , tk ): ∆ フェーズ中の更新で使われた P の始点・終点（重複を許す） Claim |{ℓ : sℓ ∈ X, tℓ ∈ / X}| ≤ |{ℓ : sℓ ∈ / X, tℓ ∈ X}| (∵) G に X の外に出る枝はないので，X から出るパスを使うには，それより前に X へ入るパスを使い，Gφ に X から出る枝を逆向き枝として作る必要がある． 45 / 47

容量スケーリング法の解析 Claim |{ℓ : sℓ ∈ X, tℓ ∈ /
X}| ≤ |{ℓ : sℓ ∈ / X, tℓ ∈ X}| よって， k = |{ℓ : sℓ , tℓ ∈ X}| + |{ℓ : sℓ ∈ X, tℓ ∈ / X}| + |{ℓ : sℓ ∈ / X, tℓ ∈ X}| + |{ℓ : sℓ , tℓ ∈ / X}| ≤ |{ℓ : sℓ , tℓ ∈ X}| + 2|{ℓ : sℓ ∈ / X, tℓ ∈ X}| + |{ℓ : sℓ , tℓ ∈ / X}| = |{ℓ : tℓ ∈ X}| + |{ℓ : sℓ ∈ / X}| ≤ |X ∩ U∆− | + |U∆+ \ X| ≤ n. 46 / 47

容量スケーリング法の解析 Claim |{ℓ : sℓ ∈ X, tℓ ∈ /
X}| ≤ |{ℓ : sℓ ∈ / X, tℓ ∈ X}| よって， k = |{ℓ : sℓ , tℓ ∈ X}| + |{ℓ : sℓ ∈ X, tℓ ∈ / X}| + |{ℓ : sℓ ∈ / X, tℓ ∈ X}| + |{ℓ : sℓ , tℓ ∈ / X}| ≤ |{ℓ : sℓ , tℓ ∈ X}| + 2|{ℓ : sℓ ∈ / X, tℓ ∈ X}| + |{ℓ : sℓ , tℓ ∈ / X}| = |{ℓ : tℓ ∈ X}| + |{ℓ : sℓ ∈ / X}| ≤ |X ∩ U∆− | + |U∆+ \ X| ≤ n. 定理 (Edmonds–Karp (1970)) 容量スケーリング法は，O(n(m + n log n) log bmax ) 時間で，最小費用 b 流を求めるか，b 流が存在しないことを判定する． 46 / 47

最小費用流: まとめまとめ • 最小費用流問題の定義，Gale の定理，負閉路最適性条件 • 逐次最短路法，主双対法，容量スケーリング法その他のアルゴリズム •
最小平均閉路消去法 O(m3 n2 log n) 時間強多項式時間 (Goldberg–Tarjan (JACM 1989)) • 費用スケーリング O(mn log(n2 /m) log(nC)) 時間 C = maxa∈A |c(a)| (Goldberg–Tarjan (Math of OR 1990)) • 現在最速 m1+o(1) 時間 (JACM 2025 1 ) 1 L. Chen, R. Kyng, Y. P. Liu, R. Peng, M. P. Gutenberg, and S. Sachdeva, “Maximum Flow and Minimum-Cost Flow in Almost-Linear Time”, JACM, 2025. 47 / 47

組合せ最適化特論第 7 回（マトロイド）担当: 相馬輔 2026/7/2 1 /
44

4 5 (5/7) 二部マッチング①（Konig-Egervary の定理，増加道アルゴリズム，ハンガリー法） (5/14) 二部マッチング②（最短路問題の復習，逐次最短路法と主双対法，最適性基準からの見方） (5/21) 最大流① （定式化，最大流最小カット定理，応用例） (5/28) 最大流②（残余ネットワーク，Ford–Fulkerson 法，Edmonds–Karp のアルゴリズム）+ 最小費用流①（定式化，輸送問題，最大流との関係） 3 / 44

各回の内容（予定） II (6/4) 休み 6 (6/11) 最小費用流②（逐次最短路法，容量スケーリング法） (6/18) 休み (6/25)
休み 7 8 9 (7/2) マトロイド（定義と公理系，貪欲法，マトロイド多面体） (7/9) 独立マッチング・マトロイド交差（定義，応用例，Edmonds の最大最小定理，増加道アルゴリズム） (7/16) 劣モジュラ関数①（諸例，劣モジュラ基多面体，Lovász 拡張，劣モジュラ最小化） (7/23) 休み 4 / 44

各回の内容（予定） III 10 (7/30) 劣モジュラ関数②（劣モジュラ最大化，近似アルゴリズム，貪欲法） 11 (どこか) 精選トピック① 12 (どこか)
精選トピック② 13 (どこか) 精選トピック③ • レポート課題を 6 月と期末に出す予定 • 精選トピックの日時は今後調整 5 / 44

目次 1. マトロイドとは・マトロイドの諸例・独立集合族・基族・
階数関数 2. 最小重み独立集合と貪欲法・最小重み独立集合問題・貪欲法・ Kruskal のアルゴリズム 3. マトロイド多面体・線形不等式系と整数性 6 / 44

マトロイドとはマトロイド (matroid; matrix + -oid) Whitney (1935), 中澤 (1935),
Pauc–Haupt–Nöbeling (1937–1940), Rado (1942) らによって独立に導入された組合せ構造．組合せ最適化におけるマトロイドの重要性基本的な組合せ最適化問題にマトロイド制約を加えることで，非自明な一般化が得られる． • 二部マッチング −→ 独立マッチング・マトロイド交差（次回） • サイズ制約劣モジュラ最大化 −→ マトロイド制約劣モジュラ最大化 • 秘書問題 −→ マトロイド秘書問題 ... 8 / 44

マトロイドの例①（分割マトロイド） E : 有限集合 (E1 , E2 , E3 ):
E の分割 ※一般に k 分割でもよい E1 E2 E3 I = {I ⊆ E : |I ∩ Ei | ≤ 1 (i = 1, 2, 3)} 集合族 I は以下の 3 つの性質を満たす: (I0) ∅ ∈ I (I1) I ∈ I , I 0 ⊆ I =⇒ I 0 ∈ I (I2) I1 , I2 ∈ I , |I1 | < |I2 | =⇒ ∃e ∈ I2 − I1 s.t. I1 + e ∈ I (I1 + e := I1 ∪ {e}) 9 / 44

マトロイドの例②（グラフ的マトロイド） G = (V, E): 無向グラフ I = {I ⊆
E : I は森 (閉路を含まない部分グラフ)} 森の例補題集合族 I は以下の 3 つの性質を満たす: (I0) ∅ ∈ I (I1) I ∈ I , I 0 ⊆ I =⇒ I 0 ∈ I (I2) I1 , I2 ∈ I , |I1 | < |I2 | =⇒ ∃e ∈ I2 − I1 s.t. I1 + e ∈ I 10 / 44

マトロイドの例③（線形マトロイド） A: （体 F 上の）r × n 行列 E =
{1, . . . , n} I I = {I ⊆ E : 列部分行列 A[I] の列は一次独立 } A[I] 補題集合族 I は以下の 3 つの性質を満たす: (I0) ∅ ∈ I (I1) I ∈ I , I 0 ⊆ I =⇒ I 0 ∈ I (I2) I1 , I2 ∈ I , |I1 | < |I2 | =⇒ ∃e ∈ I2 − I1 s.t. I1 + e ∈ I 11 / 44

補題の証明 (I0) ∅ ∈ I (I1) I ∈ I ,
I 0 ⊆ I =⇒ I 0 ∈ I (I2) I1 , I2 ∈ I , |I1 | < |I2 | =⇒ ∃e ∈ I2 −I1 s.t. I1 +e ∈ I (証明) (I0), (I1): 定義から自明． (I2): 独立集合 I1 , I2 (|I1 | < |I2 |) を取る． Claim. A[I2 ] の列のうち，A[I1 ] の列が張る部分空間に含まれないものが存在する． (∵) A[I1 ], A[I2 ] の列の張る部分空間をそれぞれ W1 , W2 とすると， dim W1 = |I1 | < |I2 | = dim W2 であるから．そのような列の添字を e ∈ I2 − I1 とすると，I1 + e は独立集合． 12 / 44

分割マトロイド ⊂ 線形マトロイド E : 有限集合 (E1 , E2 ,
E3 ): E の分割 ※一般に k 分割でもよいに対して，行列 E1 E2 E3 E2 E3   E1 1 1 1 0 0 0 0 0 0 A = 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 を考えると，A が定める線形マトロイドの独立集合族は分割マトロイドの独立集合族に一致する． 13 / 44

グラフ的マトロイド ⊂ 線形マトロイドネットワーク行列 (復習) 有向グラフ G = (V, A)
に対し， V × A 行列 B を   +1 (i は a の始点) Bi,a := −1 (i は a の終点)  0 otherwise (i ∈ V, a ∈ A) と定める． a b c d  +1 +1 +1 0 0 −1 0 0 +1 0   B=  0 −1 0 0 +1 0 0 −1 −1 −1  補題無向グラフ G = (V, E) の枝を任意に向き付けた有向グラフを考え，そのネットワーク行列を B とする．このとき，B[I] の列は一次独立 ⇐⇒ I は G の森 14 / 44

マトロイドの定義（独立集合族）定義 I2 I1 E : 有限集合, I ⊆ 2E
: 部分集合族 def M = (E, I) がマトロイド ⇐⇒ e (I0) ∅ ∈ I (I1) I ∈ I , I 0 ⊆ I =⇒ I 0 ∈ I (I2) I1 , I2 ∈ I , |I1 | < |I2 | =⇒ ∃e ∈ I2 − I1 s.t. I1 + e ∈ I 特に，I ∈ I を独立集合 (independent set) といい，I を独立集合族という．また，E をマトロイドの台集合 (ground set) という． 15 / 44

基族 M = (E, I): マトロイド定義 def • 独立集合
I が極大 (maximal) ⇐⇒ I を真に含む独立集合が存在しない • 極大な独立集合を M の基 (base) といい，基の全体を基族 (base family) という．例 • 分割マトロイドの基族: 各分割ブロック Ei から要素を 1 つずつ含む集合 • グラフ的マトロイドの基族: グラフが連結であるとすると，基はグラフの全域木 (spanning tree) 16 / 44

基族 B をマトロイドの基族とする．補題 B1 , B2 ∈ B =⇒
|B1 | = |B2 | 17 / 44

|B1 | = |B2 | (証明) 背理法．|B1 | < |B2 | とする．B1 , B2 は独立集合なので，公理 (I2) より，ある e ∈ B2 \ B1 で B1 + e ∈ I となるものが存在．これは B1 の極大性に反する． 17 / 44

|B1 | = |B2 | (証明) 背理法．|B1 | < |B2 | とする．B1 , B2 は独立集合なので，公理 (I2) より，ある e ∈ B2 \ B1 で B1 + e ∈ I となるものが存在．これは B1 の極大性に反する．基の大きさをマトロイド M の階数 (rank) といい，r(M) で表す．補題 I ∈ I , |I| = r(M) =⇒ I は基． 17 / 44

基族定理マトロイドの基族 B に対し，次が成り立つ: (B1) B 6= ∅ (B2)
B1 , B2 ∈ B , B1 6= B2 , i ∈ B1 \ B2 =⇒ ∃j ∈ B2 \ B1 s.t. B1 − i + j ∈ B . B1 B2 i j 18 / 44

基族定理マトロイドの基族 B に対し，次が成り立つ: (B1) B 6= ∅ (B2)
B1 , B2 ∈ B , B1 6= B2 , i ∈ B1 \ B2 =⇒ ∃j ∈ B2 \ B1 s.t. B1 − i + j ∈ B . B1 B2 i j (証明) (B1): 公理 (I0) ∅ ∈ I より，少なくとも 1 つは基が存在する． (B2): B1 − i と B2 は独立集合で，|B1 − i| = |B1 | − 1 < |B2 |．よって，公理 (I2) より，ある j ∈ B2 \ (B1 − i) = B2 \ B1 で (B1 − i) + j ∈ I となるものが存在． |B1 − i + j| = |B1 | なので，補題よりこれは基． 18 / 44

基族実は，基族の性質 (B1), (B2) からマトロイドを定義することもできる．補題 (cf. [Ch. 14, Korte–Vygen
(2018)]) B ⊆ 2E を (B1), (B2) を満たす集合族とする．このとき， I := {I ⊆ E : I はある B ∈ B に含まれる } とすると，I は独立集合族である．すなわち，(B1), (B2) もマトロイドの公理系である． 19 / 44

階数関数 M = (E, I): マトロイド定義 • X ⊆
E に対し，X に含まれる最大の独立集合の大きさを X の階数 (rank) といい，r(X) で表す． • r : X 7→ r(X) を階数関数 (rank function) という． 20 / 44

階数関数 M = (E, I): マトロイド定義 • X ⊆
E に対し，X に含まれる最大の独立集合の大きさを X の階数 (rank) といい，r(X) で表す． • r : X 7→ r(X) を階数関数 (rank function) という．例 • 分割マトロイド: r(X) = |{i : Ei ∩ X 6= ∅}| • グラフ的マトロイド: r(X) = |V (G[X])| − (G[X] の連結成分数) (G[X]: X の誘導部分グラフ) • 線形マトロイド: r(X) = rank A[X] 20 / 44

階数関数の性質定理マトロイドの階数関数 r は次の性質を満たす: (R1) 0 ≤ r(X) ≤
|X| (X ⊆ E ) (R2) r(X) ≤ r(Y ) (X ⊆ Y ⊆ E ) (R3) r(X) + r(Y ) ≥ r(X ∪ Y ) + r(X ∩ Y ) 単調性 (X, Y ⊆ E ) 劣モジュラ性実は，(R1)–(R3) もマトロイドの公理系となる．定理 (cf. [Ch. 14, Korte–Vygen (2018)]) (R1)–(R3) を満たす集合関数 r : 2E → Z+ に対し， I = {X ⊆ E : |X| = r(X)} はマトロイドの独立集合族． 21 / 44

定理の証明 (証明) (R1), (R2): 定義から自明． (R1) 0 ≤ r(X) ≤
|X| (R2) r(X) ≤ r(Y ) (X ⊆ Y ⊆ E ) (R3) r(X) + r(Y ) ≥ r(X ∪ Y ) + r(X ∩ Y ) (R3): IX∩Y を X ∩ Y の最大独立集合とする．公理 (I2) より，IX∩Y X に X ∪ Y の要素を加えて，X ∪ Y の最大独立集合 IX∪Y を作れる．このとき， • IX∩Y = IX∪Y ∩ (X ∩ Y ) (X, Y ⊆ E ) Y X ∩Y • IX∪Y ∩ X は X の独立集合，IX∪Y ∩ Y は Y の独立集合．よって， r(X) + r(Y ) ≥ |IX∪Y ∩ X| + |IX∪Y ∩ Y | = |IX∪Y ∩ (X ∪ Y )| + |IX∪Y ∩ (X ∩ Y )| = |IX∪Y | + |IX∩Y | = r(X ∪ Y ) + r(X ∩ Y ) 22 / 44

最小重み独立集合問題 • E 上のマトロイド M = (E, I) • 台集合上の重み
w : E → R • 非負整数 0 ≤ k ≤ r(M) 最小重み独立集合問題 (Minimum Weight Independent Set Problem) minimize w(I) s.t. I ∈ I, |I| = k この節の目標: 最小重み独立集合問題は貪欲法 (greedy algorithm) で解けることを示す． 24 / 44

例：最小重み全域木問題 • G = (V, E) 連結無向グラフ • w :
E → R 枝重み最小重み全域木問題 (Minimum Weight Spanning Tree Problem) minimize w(T ) s.t. T は G の全域木全域木の例これは • M = G のグラフ的マトロイド • k = |V | − 1 = r(M) に対する最小重み独立集合問題． 25 / 44

例 8 7 4 9 2 11 4 7 8
6 1 14 10 2 26 / 44

貪欲法 X0 := ∅, k := 0. 2: E の要素を
w の昇順に並べる: w(e1 ) ≤ · · · ≤ w(en ) (n = |E|). 3: for i = 1, . . . , n : 4: Xk + ei ∈ I ならば ei を Xk に追加し，k ← k + 1 とする． 1: // Xk は大きさ k の独立集合定理 k = 0, 1, . . . , r(M) に対し，Xk が存在し，かつ Xk は大きさ k の独立集合のうち重み最小である． 27 / 44

Kruskal のアルゴリズム特に最小重み全域木問題に適用したものは Kruskal のアルゴリズムと呼ばれる． X := ∅. 2:
枝を w の昇順に並べる: w(e1 ) ≤ · · · ≤ w(em ) (m = |E|). 3: for i = 1, . . . , m : 4: X + ei が閉路を含まないならば ei を X に追加する． 5: return X 1: 系 X は最小重み全域木である． 28 / 44

例 8 7 4 9 2 11 4 7 8
6 1 14 10 2 29 / 44

定理の証明補題貪欲法の任意の時点の暫定解 X に対して，次が成り立つ: e∈ / X , X
+ e ∈ I =⇒ e はまだ調べていない要素． 30 / 44

+ e ∈ I =⇒ e はまだ調べていない要素． (証明) e は既に調べた要素だと仮定する．e を調べたときの暫定解を X 0 ⊆ X とすると，X 0 + e ⊆ X + e ∈ I より，X 0 + e ∈ I . よって，貪欲法は e を X 0 に追加したことになり，e ∈ X となって矛盾． 30 / 44

+ e ∈ I =⇒ e はまだ調べていない要素． (証明) e は既に調べた要素だと仮定する．e を調べたときの暫定解を X 0 ⊆ X とすると，X 0 + e ⊆ X + e ∈ I より，X 0 + e ∈ I . よって，貪欲法は e を X 0 に追加したことになり，e ∈ X となって矛盾．補題 k = 0, 1, . . . , r(M) に対し，Xk が存在する． 30 / 44

+ e ∈ I =⇒ e はまだ調べていない要素． (証明) e は既に調べた要素だと仮定する．e を調べたときの暫定解を X 0 ⊆ X とすると，X 0 + e ⊆ X + e ∈ I より，X 0 + e ∈ I . よって，貪欲法は e を X 0 に追加したことになり，e ∈ X となって矛盾．補題 k = 0, 1, . . . , r(M) に対し，Xk が存在する． (証明) k < r(M) とし，Xk が存在すると仮定する．k = |Xk | < r(M) より，Xk は基ではないから，e ∈ / Xk で Xk + e ∈ I となるものが存在． 30 / 44

+ e ∈ I =⇒ e はまだ調べていない要素． (証明) e は既に調べた要素だと仮定する．e を調べたときの暫定解を X 0 ⊆ X とすると，X 0 + e ⊆ X + e ∈ I より，X 0 + e ∈ I . よって，貪欲法は e を X 0 に追加したことになり，e ∈ X となって矛盾．補題 k = 0, 1, . . . , r(M) に対し，Xk が存在する． (証明) k < r(M) とし，Xk が存在すると仮定する．k = |Xk | < r(M) より，Xk は基ではないから，e ∈ / Xk で Xk + e ∈ I となるものが存在．前補題より，e は Xk が定義された時点で，まだ調べていない要素である．よって，少なくとも 1 つは Xk に追加できる要素がまだ残っているので，Xk+1 が定義される． 30 / 44

定理の証明補題 k = 0, 1, . . . ,
r(M) に対し，Xk は大きさ k の最小重み独立集合． 31 / 44

定理の証明補題 k = 0, 1, . . . ,
r(M) に対し，Xk は大きさ k の最小重み独立集合． (証明) 背理法．Xk より真に重みの小さい大きさ k の独立集合 Y が存在すると仮定． Xk = {x1 , . . . , xk } (w(x1 ) ≤ · · · ≤ w(xk )) Y = {y1 , . . . , yk } (w(y1 ) ≤ · · · ≤ w(yk )) とする． w(Y ) < w(Xk ) より，ある 1 ≤ i ≤ k で w(yi ) < w(xi ) が成り立つ． < x1 ≤ · · · ≤ xi−1 ≤ xi ≤ · · · ≤ xk y1 ≤ · · · ≤ yi−1 ≤ yi ≤ · · · ≤ yk 31 / 44

定理の証明（続き） x1 ≤ · · · ≤ xi−1 ≤ xi
≤ · · · ≤ xk Yi y1 ≤ · · · ≤ yi−1 ≤ yi ≤ · · · ≤ yk < Xi−1 独立集合 Xi−1 と Yi に公理 (I2) を適用すると，ある y ∈ Yi \ Xi−1 で Xi−1 + y ∈ I となるものが存在する．補題より，y は xi を調べる時点（暫定解 Xi−1 ）でまだ調べられていないので， w(y) ≥ w(xi ) が成立．一方，w(y) ≤ w(yi ) < w(xi ) なので，矛盾． 32 / 44

貪欲法の計算量一般に，マトロイド M = (E, I) は |E| に対し指数個の独立集合を持つため，独立集合の一覧をアルゴリズムに入力することはできない．
独立性オラクル X ∈ I か? 部分集合 X ⊆ E を入力すると，X が独立集合か否かを返してくれるオラクル YES/NO 具体的なマトロイド（グラフ的マトロイドや線形マトロイドなど）では，グラフの操作や行列計算により多項式時間で実装できる． 33 / 44

貪欲法の計算量一般に，マトロイド M = (E, I) は |E| に対し指数個の独立集合を持つため，独立集合の一覧をアルゴリズムに入力することはできない．
独立性オラクル X ∈ I か? 部分集合 X ⊆ E を入力すると，X が独立集合か否かを返してくれるオラクル YES/NO 具体的なマトロイド（グラフ的マトロイドや線形マトロイドなど）では，グラフの操作や行列計算により多項式時間で実装できる．定理貪欲法は O(n log n + nIO) 時間で最小重み独立集合を求める．ただし，n = |E|， IO は独立性オラクルの計算時間． 33 / 44

マトロイド多面体定義マトロイド M のマトロイド多面体 (matroid polytope) を次で定める: P (M)
:= conv{1I : I ∈ I} ⊆ RE (1I ∈ {0, 1}E : I の特性ベクトル) この節の目標定理 (Edmonds (1970)) P (M) = {x ∈ RE : x(X) ≤ rM (X) (X ⊆ E), x ≥ 0} 35 / 44

マトロイド多面体の例例 (グラフ的マトロイド) 連結な無向グラフ G = (V, E) に対するグラフ的マトロイドのマトロイド多面体は次で表される:
x(X) ≤ |V (G[X])| − c(G[X]) (X ⊆ E) x≥0 (G[X]: X の誘導部分グラフ, c(G[X]): G[X] の連結成分数) 36 / 44

定理の証明 (1/4) P := {x ∈ RE : x(X) ≤
rM (X) (X ⊆ E), x ≥ 0} とする． P (M) ⊆ P であること: I ∈ I を独立集合とし，x = 1I を特性ベクトルとする．任意の部分集合 X ⊆ V に対し， x(X) = |I ∩ X| ≤ rM (X). (I ∩ X ⊆ X は独立集合より) ∴ x ∈ P . P は凸多面体なので，P (M) ⊆ P . 37 / 44

定理の証明 (2/4) P ⊆ P (M) であること: 任意の w ∈
RE に対し，maxx∈P w> x を達成する点が P (M) に存在することを示す． w を重みとする最大重み独立集合問題を考える: maximize w(I) s.t. I ∈ I 重みを降順に並べて， w(e1 ) ≥ w(e2 ) ≥ · · · ≥ w(ek ) ≥ 0 > w(ek+1 ) ≥ · · · ≥ w(en ) とすると，e1 , . . . , ek まで貪欲法を走らせた暫定解が最適解である．それを I = {ei1 , ei2 , . . . , eiℓ } (1 ≤ i1 < i2 < · · · < iℓ ≤ k) とおく．x = 1I ∈ P (M) が maxx∈P w> x の最適解であることを示せば良い． 38 / 44

定理の証明 (3/4) 主問題 (P) max ∑ w(e)x(e) e∈E s.t. ∑
x(e) ≤ r(X) (X ⊆ E) e∈X x(e) ≥ 0 (e ∈ E) 双対問題 (D) min ∑ r(X)yX X⊆E s.t. ∑ yX ≥ w(e) (e ∈ E) X∈e yX ≥ 0 (X ⊆ E) 39 / 44

定理の証明 (4/4) LP の一般論より， x = 1I が主最適解であることを示すには，強双対性 ∑ w>
x = X⊆E r(X)yX を満たす双対実行可能解 y を構成すればよい．実際，   w(eij ) − w(eij+1 ) if S = {ei1 , . . . , eij } (j = 1, . . . , ℓ − 1) yS := w(eiℓ ) if S = {ei1 , . . . , eiℓ }  0 otherwise とすると，y は双対実行可能で，(x, y) が強双対性を満たすことが，直接計算により確認できる（各自確認せよ）． 40 / 44

マトロイド多面体上の線形最適化系マトロイド多面体上の線形最適化 max w> x s.t. x(X) ≤ rM
(X) (X ⊆ E), x ≥ 0 は O(n log n + nIO) 時間で最適解を求められる．指数本の不等式があるにもかかわらず，貪欲法で最適解を求められる． 41 / 44

マトロイド多面体の整数性系不等式系 {x(X) ≤ rM (X) (X ⊆ E),
x ≥ 0} は整数多面体を定める． P (M) を定める不等式系の係数行列は完全単模行列ではない！   1 1 1 1 0 (∵) たとえば 0 0 1 のように，行列式 = 2 の部分行列を含んでいる． 1 マトロイド多面体は完全単模性に依らず，整数性が証明できる． 42 / 44

マトロイド基多面体基についても同様の定理が成り立つ．定義マトロイド M の基多面体 (base polytope) を次で定める: B(M)
:= conv{1B : B ∈ B} ⊆ RE (1B ∈ {0, 1}E : B の特性ベクトル) 定理 (Edmonds (1970)) B(M) = {x ∈ RE : x(X) ≤ rM (X) (X ⊆ E), x(E) = rM (E) , x ≥ 0} 43 / 44

組合せ最適化特論第 8 回（独立マッチング・マトロイド交差）担当: 相馬輔 2026/1/29 1 /
35

目次 1. 独立マッチング・定義・マトロイド交差・最大最小定理 2.
サーキット・サーキット族・基本サーキット・交換可能性 3. アルゴリズム・増加道アルゴリズム・最大最小定理の証明 2 / 35

独立マッチング G = (V + , V − ; E):
二部グラフ M+ = (V + , I + ): V + 上のマトロイド M− = (V − , I − ): V − 上のマトロイド V− V+ M ∂ +M ∂ −M 定義マッチング M が独立マッチング def ⇐⇒ ∂ + M ∈ I + かつ ∂ − M ∈ I − (∂ + M , ∂ − M : それぞれ M に接続する V + , V − の頂点集合) 独立マッチング問題 maximize |M | I + = 2V , I − = 2V + − subject to M は独立マッチングのとき，通常の二部マッチング問題． 4 / 35

マトロイド交差 M1 = (E, I1 ), M2 = (E, I2
): 同じ台集合 E 上のマトロイドマトロイド交差 maximize |I| subject to I ∈ I1 ∩ I2 5 / 35

マトロイド交差 M1 = (E, I1 ), M2 = (E, I2
): 同じ台集合 E 上のマトロイドマトロイド交差 maximize |I| subject to I ∈ I1 ∩ I2 右の二部グラフ G と，(M+ , M− ) = (M1 , M2 ) に対する独立マッチング問題と等価 E E 注実は独立マッチングをマトロイド交差に帰着できることも知られており，互いに等価な問題である． 5 / 35

独立マッチングの最大最小定理 S− S + ⊆ V + , S −
⊆ V − が頂点被覆 def ⇐⇒ 任意の枝 e = ij ∈ E に対し，i ∈ S + または j ∈ S − . S + 6 / 35

独立マッチングの最大最小定理 S− S + ⊆ V + , S −
⊆ V − が頂点被覆 def ⇐⇒ 任意の枝 e = ij ∈ E に対し，i ∈ S + または j ∈ S − . S + 補題 (弱双対性) r+ , r− をそれぞれ，マトロイド M+ , M− の階数関数とする．任意の独立マッチング M と頂点被覆 (S + , S − ) に対し，|M | ≤ r+ (S + ) + r− (S − ). (証明) |M | ≤ |∂ + M ∩ S + | + |∂ − M ∩ S − | ≤ r+ (S + ) + r− (S − ) 6 / 35

独立マッチングの最大最小定理今日の目標: 以下の最大最小定理をアルゴリズム的に証明し，主・双対最適解が多項式時間で求められることを示す．定理 (Welsh (1970)) max M :
独立マッチング |M | = + min − (S , S ): 頂点被覆 r+ (S + ) + r− (S − ) これは，Kőnig–Egerváry の定理（第２回）の一般化である．定理 (Kőnig–Egerváry) max M : マッチング |M | = min (S + , S − ): 頂点被覆 |S + | + |S − | 7 / 35

マトロイド交差の最大最小定理定理をマトロイド交差の場合に適用すると，以下の定理が得られる．定理 (Edmonds (1970)) max |I| = min r1
(X) + r2 (E \ X) I∈I1 ∩I2 X⊆E 8 / 35

マトロイド交差の最大最小定理定理をマトロイド交差の場合に適用すると，以下の定理が得られる．定理 (Edmonds (1970)) max |I| = min r1
(X) + r2 (E \ X) I∈I1 ∩I2 X⊆E (証明) 帰着に用いた二部グラフにおいて，任意の X ⊆ E に対して (S + , S − ) = (X, E \ X) は頂点被覆． X + − + 逆に，任意の頂点被覆 (S , S ) に対し，X = S とすると，頂点被覆の定義から E \ X ⊆ S − ．階数関数の単調性より，r2 (E \ X) ≤ r− (S − ) なので，右辺の最小化においては (X, E \ X) の形の頂点被覆だけ考えれば十分． E\X 8 / 35

（参考）重み付き独立マッチング w : E → R: 重み, k ∈ Z+
重み付き独立マッチング maximize w(M ) subject to M 独立マッチング, |M | = k 重み付きマトロイド交差 maximize w(I) subject to I ∈ I1 ∩ I2 , |I| = k 事実重み付き独立マッチング/マトロイド交差も多項式時間で解ける． (cf. [§13.7 Korte–Vygen, 2018]) 9 / 35

応用例①: k 独立集合問題 k 森問題連結無向グラフ G = (V, E)
と，非負整数 k ∈ Z+ に対し，G を k 個の枝素な森に分割できるか？できるなら，そのような分割を求めよ． k = 2 の例 10 / 35

応用例①: k 独立集合問題より一般に: k 独立集合問題台集合上 E 上のマトロイド M1
, . . . , Mk に対し，台集合 E を E = I1 ∪ · · · ∪ Ik (Ii ∈ Ii ) と k 個の独立集合へ分割できるか？できるなら，そのような分割を求めよ．定理 k 独立集合問題は独立マッチングへ帰着することで，多項式時間で解ける． 11 / 35

マトロイドの直和定義 M1 = (E1 , I1 ), M2 =
(E2 , I2 ): 台集合が互いに素なマトロイドこのとき， I = {I1 ⊕ I2 : I1 ∈ I1 , I2 ∈ I2 } は E1 ⊕ E2 上のマトロイドの独立集合族になる．これを M1 と M2 の直和 (direct sum) といい，M1 ⊕ M2 で表す． k 個のマトロイドの直和も同様に定義でき，M1 ⊕ · · · ⊕ Mk で表す． 12 / 35

k 独立集合問題→独立マッチングへの帰着定理 k 独立集合問題は独立マッチングへ帰着することで，多項式時間で解ける． 13 / 35

k 独立集合問題→独立マッチングへの帰着定理 k 独立集合問題は独立マッチングへ帰着することで，多項式時間で解ける． (証明) 右図の二部グラフを考える．頂点集合は V + =
E1 ⊕ · · · ⊕ Ek (各 Ei は E のコピー) E1 − V =E であり，各枝はオリジナルの要素 e ∈ E と各コピー e ∈ Ei (i = 1, . . . , k ) を結んでいる． V + , V − 上のマトロイドを次のように定める: M + = M1 ⊕ · · · ⊕ Mk − M− = (V − , 2V ) .. . E Ek このとき，大きさ |E| の独立マッチング ←→ 独立集合への分割 E = I1 ∪ · · · ∪ Ik 13 / 35

応用例②: 最小重み全域有向木定義有向グラフ D = (V, A) の部分グラフ T
が，r ∈ V を根とする全域有向木 (spanning arborescence) def ⇐⇒ r • 枝の向きを無視すると T は全域木 • 任意の頂点 v ∈ V − r に対し，ρT (v) = 1 r を根とする全域有向木の例 (ρT (v): T における v の入次数) 最小重み全域有向木問題 w : A → R: 枝重み minimize w(T ) subject to T は r を根とする全域有向木 14 / 35

重み付きマトロイド交差への帰着枝集合 A 上のマトロイド M1 , M2 を次のように定める: r •
M1 := G の向きを無視した無向グラフに対するグラフ的マトロイド • M2 := (In(r), 2In(r) ) ⊕ (分割 {In(v) : v ∈ V − r} に対する分割マトロイド) T ⊆ A が全域有向木 ⇐⇒ T ∈ I1 ∩ I2 かつ |T | = |V | − 1 よって，最小重み全域有向木問題は重み付きマトロイド交差に帰着でき，多項式時間で解ける． 15 / 35

サーキット定義 def • X ⊆ E が従属集合 (dependent set)
⇐⇒ X∈ / I. • C ⊆ E がサーキット (circuit) def ⇐⇒ C ∈ / I かつ C の任意の真部分集合 C ′ ⊊ C は C ′ ∈ I すなわち，サーキットは極小な従属集合． 17 / 35

サーキット定義 def • X ⊆ E が従属集合 (dependent set)
⇐⇒ X∈ / I. • C ⊆ E がサーキット (circuit) def ⇐⇒ C ∈ / I かつ C の任意の真部分集合 C ′ ⊊ C は C ′ ∈ I すなわち，サーキットは極小な従属集合． • X が独立集合 ⇐⇒ X はサーキットを含まない．例グラフ的マトロイドのサーキット = グラフの単純閉路 17 / 35

サーキット定理サーキット族 C は以下の性質を満たす: (C1) C1 , C2 ∈
C , C1 ⊆ C2 =⇒ C1 = C2 (C2) C1 , C2 ∈ C (C1 ̸= C2 ), e ∈ C1 ∩ C2 =⇒ (C1 ∪ C2 ) − e はサーキットを含む． (C1 ∪ C2 ) − e := (C1 ∪ C2 ) \ {e} C1 e C2 18 / 35

定理の証明 (C1) C1 , C2 ∈ C , C1 ⊆
C2 =⇒ C1 = C2 (C2) C1 , C2 ∈ C (C1 ̸= C2 ), e ∈ C1 ∩ C2 =⇒ (C1 ∪ C2 ) − e はサーキットを含む． (C1): 極小性から明らか． (C2): C1 ̸= C2 と (C1) から要素 f ∈ C1 \ C2 が存在する．極小性から C1 − f は独立集合である．C1 − f に C2 \ C1 の要素を追加して C1 ∪ C2 に含まれる最大の独立集合 B を作る． B は独立集合なのでサーキット C2 を含むことはできないから， C2 C1 f e |B| < |C1 ∪ C2 | − 1 = |(C1 ∪ C2 ) − e|. B は C1 ∪ C2 に含まれる最大の独立集合であったから，それより大きい (C1 ∪ C2 ) − e は従属集合であり，したがってサーキットを含む． 19 / 35

基本サーキット補題独立集合 I と y ∈ / I, I
+ y ∈ / I に対し，I + y は y を含むサーキットをただ 1 つ含む．これを I と y に対する基本サーキット (fundamental circuit) といい，C(I, y) と書く． y C(I, y) 20 / 35

補題の証明 (C1) C1 , C2 ∈ C , C1 ⊆
C2 =⇒ C1 = C2 (C2) C1 , C2 ∈ C (C1 ̸= C2 ), e ∈ C1 ∩ C2 =⇒ (C1 ∪ C2 ) − e はサーキットを含む． [存在性] I + y は従属なので，サーキット C を含む．I は独立なので C ⊆ I ではあり得ないから，y ∈ C である． [一意性] もしこのようなサーキットが C1 , C2 (C1 ̸= C2 ) の 2 つあったとすると，(C2) より (C1 ∪ C2 ) − y ⊆ I がサーキットを含むことになってしまい，I の独立性に反する． 21 / 35

基本サーキットと交換可能性補題 I ∈ I, x ∈ I, y ∈
/ I, I + y ∈ / I とする．このとき， x ∈ C(I, y) ⇐⇒ I − x + y ∈ I . y (証明) 前補題より，I + y は唯一のサーキット C(I, y) を含む．x ∈ C(I, y) より， I − x + y は C(I, y) を含まないから，独立集合である．逆も同様． C(I, y) x 22 / 35

逐次交換可能性 I − x1 + y1 ∈ I かつ I
− x2 + y2 ∈ I ならば， I \ {x1 , x2 } ∪ {y1 , y2 } ∈ I か？ 23 / 35

逐次交換可能性 I − x1 + y1 ∈ I かつ I
− x2 + y2 ∈ I ならば， I \ {x1 , x2 } ∪ {y1 , y2 } ∈ I か？一般には正しくない y1 y1 C(I, y1 ) x1 x2 C(I, y2 ) y2 y2 23 / 35

逐次交換可能性補題 (逐次交換補題) I ∈ I , x1 , .
. . , x s ∈ I , y1 , . . . , y s ∈ / I に対し， 1 I + yk ∈ / I , xk ∈ C(I, yk ) 2 xj ∈ / C(I, yk ) (k = 1, . . . , s) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (xk , yk ) は交換可能 (1 ≤ j < k ≤ s) とする．このとき，I \ {x1 , . . . , xs } ∪ {y1 , . . . , ys } ∈ I . y1 x1 C(I, y1 ) x2 C(I, y2 ) y2 24 / 35

逐次交換可能性の証明 1 I + yk ∈ / I , xk
∈ C(I, yk ) 2 xj ∈ / C(I, yk ) (k = 1, . . . , s) (1 ≤ j < k ≤ s ) (証明) Ik := I \ {x1 , . . . , xk } ∪ {y1 , . . . , yk } (k = 0, . . . , s) とおく． Ik ∈ I を k に関する帰納法で示す． k = 0 のときは Ik = I より自明． k > 0 とし，Ik−1 ∈ I とする．Ik−1 + yk ∈ I なら， Ik = Ik−1 + yk − xk ∈ I より OK．Ik−1 + yk ∈ / I の場合を考える． C := C(Ik−1 , yk ) を基本サーキットとする．xk ∈ C を示せばよい．仮定②より x1 , . . . , xk−1 ∈ / C(I, yk ) なので，C(I, yk ) ⊆ Ik−1 + yk . 基本サーキットの一意性より C = C(I, yk ) ∋ xk . ① 25 / 35

独立マッチング G = (V + , V − ; E):
二部グラフ M+ = (V + , I + ): V + 上のマトロイド M− = (V − , I − ): V − 上のマトロイド V− V+ M ∂ +M ∂ −M 定義マッチング M が独立マッチング def ⇐⇒ ∂ + M ∈ I + かつ ∂ − M ∈ I − (∂ + M , ∂ − M : それぞれ M に接続する V + , V − の頂点集合) 独立マッチング問題 maximize |M | I + = 2V , I − = 2V + − subject to M は独立マッチングのとき，通常の二部マッチング問題． 27 / 35

補助ネットワーク独立マッチング M に対し，補助ネットワーク DM を以下のように定義する: A− • 頂点集合:
V + , V − （元のグラフと同じ） − → ← − • 枝集合: AM := E ∪ M ∪ A+ ∪ A− − → E := {(i, j) : ij ∈ E}. . . . . . E の準向き枝 ← − M := {(j, i) : ij ∈ M }. . . . . . M の逆向き枝 A+ := {(i, j) : ∂ + M + j ∈ / I + , i ∈ C(∂ + M, j) − j} A+ DM + . . . . . . M の交換可能性を表す枝 − A := {(i, j) : ∂ − M + i ∈ / I − , j ∈ C(∂ − M, i) − i} . . . . . . M− の交換可能性を表す枝 28 / 35

補助ネットワーク補助ネットワーク DM の頂点部分集合を次のように定める． U+ A− • U +
:= {i ∈ V + \ ∂ + M : ∂ + M + i ∈ I + } • U − := {j ∈ V − \ ∂ − M : ∂ − M + j ∈ I − } . . . . . . . . . . . . . . . . . . . . . . ∂ + M, ∂ − M に追加できる要素の集合 A+ U− DM 29 / 35

補助ネットワーク補助ネットワーク DM の頂点部分集合を次のように定める． U+ A− • U +
:= {i ∈ V + \ ∂ + M : ∂ + M + i ∈ I + } • U − := {j ∈ V − \ ∂ − M : ∂ − M + j ∈ I − } . . . . . . . . . . . . . . . . . . . . . . ∂ + M, ∂ − M に追加できる要素の集合パスによるマッチングの増大 DM 上の U + –U − パス P に対し，P に沿って M の枝を反転させたマッチングを M ′ とする．（ただし，A+ や A− の枝 A+ U− DM は反転させない）定義から，|M ′ | = |M | + 1. 29 / 35

増加道アルゴリズム定理 • M が独立マッチングで，P が枝数最小の U + –U −
パスならば， M ′ は独立マッチング． • U + –U − パスが存在しないとき，X を DM において U + から到達可能な頂点集合とすると，(V + \ X, V − ∩ X) は頂点被覆で，かつ強双対性 |M | = r+ (V + \ X) + r− (V − ∩ X) を満たす．したがって，M は最大独立マッチングで， (V + \ X, V − ∩ X) は階数最小頂点被覆である． 30 / 35

増加道アルゴリズム定理より，以下のようなアルゴリズムが得られる．増加道アルゴリズム 1: M ← ∅ とする． + −
2: while DM に U –U パスが存在する : 3: 枝数最小の U + –U − パス P を求める． // 幅優先探索で発見可能 4: P に沿って枝を反転して，より大きな独立マッチング M を得る． + 5: X を DM において U から到達可能な頂点集合とする． + 6: return M , (V \ X, V − ∩ X) 二部マッチングに対する増加道アルゴリズムの一般化． 31 / 35

定理の証明 (1/2) U+ [M ′ が独立マッチングであること] x0 : P の始点
(x1 , y1 ), . . . , (xs , ys ): P 上の A+ 枝（この順で現れる） ∂ + M ′ = (∂ + M + x0 ) \ {x1 , . . . , xs } ∪ {y1 , . . . , ys } I := ∂ + M + x0 と x1 , . . . , xs , y1 , . . . , ys が逐次交換補題の条件を満たすことを確かめればよい． x0 x1 y1 × x2 y2 32 / 35

定理の証明 (1/2) U+ [M ′ が独立マッチングであること] x0 : P の始点
(x1 , y1 ), . . . , (xs , ys ): P 上の A+ 枝（この順で現れる） ∂ + M ′ = (∂ + M + x0 ) \ {x1 , . . . , xs } ∪ {y1 , . . . , ys } I := ∂ + M + x0 と x1 , . . . , xs , y1 , . . . , ys が逐次交換補題の条件を満たすことを確かめればよい． x0 x1 y1 × x2 y2 基本サーキットの一意性から，C(∂ + M, yk ) = C(I, yk ) (k = 1, . . . , s) に注意する． ①は交換可能性枝 A+ の定義から，②は P が枝数最小なのでショートカットが存在しないことから従う． ∴逐次交換補題より，∂ + M ′ ∈ I + . 同様にして，∂ − M ′ ∈ I − も示せる． 32 / 35

定理の証明 (2/2) [(V + \ X, V − ∩ X)
が階数最小頂点被覆であること] (S + , S − ) := (V + \ X, V − ∩ X) とする．これが頂点被覆であることは二部マッチングのところで既にやった． S+ U− X S− U+ 33 / 35

定理の証明 (2/2) [(V + \ X, V − ∩ X)
が階数最小頂点被覆であること] (S + , S − ) := (V + \ X, V − ∩ X) とする．これが頂点被覆であることは二部マッチングのところで既にやった． • X から出る A+ の枝が存在しないことから，任意の i ∈ S + \ ∂ + M に対し，C(∂ + M, i) ⊆ S + S+ • 任意の i ∈ S \ ∂ M に対し，∂ M ∩ S + i はサー X キット C(∂ + M, i) を含むから，従属集合． + + + U− + ∴ ∂ + M ∩ S + は S + の最大独立集合．同様に，∂ − M ∩ S − は S − の最大独立集合． S− U+ 33 / 35

定理の証明 (2/2) [(V + \ X, V − ∩ X)
が階数最小頂点被覆であること] (S + , S − ) := (V + \ X, V − ∩ X) とする．これが頂点被覆であることは二部マッチングのところで既にやった． • X から出る A+ の枝が存在しないことから，任意の i ∈ S + \ ∂ + M に対し，C(∂ + M, i) ⊆ S + S+ • 任意の i ∈ S \ ∂ M に対し，∂ M ∩ S + i はサー X キット C(∂ + M, i) を含むから，従属集合． + + + U− + ∴ ∂ + M ∩ S + は S + の最大独立集合．同様に，∂ − M ∩ S − は S − の最大独立集合． S− U+ r+ (S + ) + r− (S − ) = |∂ + M ∩ S + | + |∂ − M ∩ S − | = |M | 33 / 35

増加道アルゴリズムの計算量 n := |V |, m := |E|, IO :=
マトロイド M+ , M− の独立性オラクルの計算量とする． 1 反復あたりの計算量: • 補助ネットワーク DM の構築: O(n2 IO + m) • U + –U − パスの探索: O(n2 + m) また，全体では高々 n/2 反復．定理独立マッチング問題は O(n3 IO + mn) 時間で解ける． 34 / 35

まとめ: 独立マッチングまとめ • 独立マッチング・マトロイド交差の定式化 • 最大最小定理 • 増加道アルゴリズム発展
• 伊理・富沢 (JORSJ, 1976): 重みつき独立マッチングに対する逐次最短路・主双対法 • Gabow–Xu (1996): 線形マトロイド交差に対する高速化 35 / 35

組合せ最適化特論第 9 回（劣モジュラ関数①）担当: 相馬輔 2026/7/14 1 /
33

4 5 (5/7) 二部マッチング①（Konig-Egervary の定理，増加道アルゴリズム，ハンガリー法） (5/14) 二部マッチング②（最短路問題の復習，逐次最短路法と主双対法，最適性基準からの見方） (5/21) 最大流① （定式化，最大流最小カット定理，応用例） (5/28) 最大流②（残余ネットワーク，Ford–Fulkerson 法，Edmonds–Karp のアルゴリズム）+ 最小費用流①（定式化，輸送問題，最大流との関係） 3 / 33

各回の内容（予定） II (6/4) 休み 6 (6/11) 最小費用流②（逐次最短路法，容量スケーリング法） (6/18) 休み (6/25)
休み 7 8 9 10 (7/2) マトロイド（定義と公理系，貪欲法，マトロイド多面体） (7/9) 独立マッチング・マトロイド交差（定義，応用例，Edmonds の最大最小定理，増加道アルゴリズム） (7/14) 劣モジュラ関数①（諸例，劣モジュラ基多面体，Lovász 拡張，劣モジュラ最小化） (7/16) 劣モジュラ関数②（劣モジュラ最大化，近似アルゴリズム，貪欲法） 4 / 33

各回の内容（予定） III 11 (7/24) 精選トピック① 12 (7/28) 精選トピック② 13 (7/30)
精選トピック③ • レポート課題を 6 月と期末に出す予定 5 / 33

目次 1. 劣モジュラ関数・定義・諸例 2. 基多面体と Lovász
拡張・基多面体・貪欲法・ Lovász 拡張 3. 最小ノルム点法・パラメトリック劣モジュラ最小化・ L2 正則化 Lovász 拡張最小化・最小ノルム点法 6 / 33

劣モジュラ関数 f : 2V → R が劣モジュラ関数 def ⇐⇒ f
(X) + f (Y ) ≥ f (X ∪ Y ) + f (X ∩ Y ) (∀X, Y ⊆ V ) 8 / 33

劣モジュラ関数 f : 2V → R が劣モジュラ関数 def ⇐⇒ f
(X) + f (Y ) ≥ f (X ∪ Y ) + f (X ∩ Y ) ⇐⇒ ∀X ⊆ ∀Y ⊆ V , ∀a ∈ V \ Y , f (X ∪ a) − f (X) ≥ f (Y ∪ a) − f (Y ) 小さい集合の増分 (∀X, Y ⊆ V ) 限界効用逓減性大きい集合の増分 X a Y 8 / 33

劣モジュラ関数 • f1 , f2 劣モジュラ関数, α1 , α2 ≥
0 =⇒ α1 f1 + α2 f2 も劣モジュラ関数 9 / 33

0 =⇒ α1 f1 + α2 f2 も劣モジュラ関数 • 特に， f (X) + f (Y ) = f (X ∪ Y ) + f (X ∩ Y ) (∀X, Y ⊆ V ) が成り立つ場合，f をモジュラ関数という．例: f (X) = |X| や，重み w : E → R に対する f (X) = w(X) など． 9 / 33

0 =⇒ α1 f1 + α2 f2 も劣モジュラ関数 • 特に， f (X) + f (Y ) = f (X ∪ Y ) + f (X ∩ Y ) (∀X, Y ⊆ V ) が成り立つ場合，f をモジュラ関数という．例: f (X) = |X| や，重み w : E → R に対する f (X) = w(X) など． • −f が劣モジュラである関数を優モジュラ関数という．すなわち， f (X) + f (Y ) ≤ f (X ∪ Y ) + f (X ∩ Y ) (∀X, Y ⊆ V ) が成り立つ関数． 9 / 33

例 1: 被覆関数 (coverage function) G = (V + ,
V − ; E) ... 2 部グラフ X Γ(X) f (X) = |Γ(X)| (Γ(X): X ⊆ V + の隣接頂点) 10 / 33

例 1: 被覆関数 (coverage function) G = (V + ,
V − ; E) ... 2 部グラフ X Γ(X) f (X) = |Γ(X)| (Γ(X): X ⊆ V + の隣接頂点) 重み付き版 w : V − → R+ : 非負重み f (X) = w(Γ(X)) 10 / 33

例 2: 凹関数と線形関数の合成 φ V = {1, . . .
, n} φ : [0, +∞) → R ... 凹関数 w : V → R+ ... 非負重み f (X) = φ(w(X)) √ • f (X) = w(X) など f (a | Y ) f (a | X) +wa w(X) +wa w(Y ) 11 / 33

例 3: グラフのカット関数 Out(X) 有向カット関数 G = (V, A) ...
有向グラフ u : A → R+ ... 非負枝重み f (X) = u(Out(X)) (X ⊆ V ) X E[X, X̄] 無向カット関数 G = (V, E) ... 無向グラフ u : E → R+ ... 非負枝重み f (X) = u(E[X, X̄]) (X ⊆ V ) X 12 / 33

限界効用逓減性記号 f (a | X) := f (X ∪
a) − f (X) (X ⊆ V , a ∈ V \ X ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X に a を追加したときの増分補題 f : 2V → R が劣モジュラ ⇐⇒ f (a | X) ≥ f (a | Y ) (∀X ⊆ ∀Y ⊆ V , ∀a ∈ V \ Y ) (証明) [ =⇒ ] X ∪ a と Y に対し，劣モジュラ性を使うと f (X ∪ a) + f (Y ) ≥ f ((X ∪ a) ∪ Y ) + f ((X ∪ a) ∩ Y ) = f (Y ∪ a) + f (X). 移項すると限界効用逓減性が出る． 13 / 33

証明の続き [ ⇐= ] 任意の X, Y ⊆ V を取る．Y
\ X = ∅ の場合は自明なので， X Y \ X ̸= ∅ と仮定して良い．Y \ X = {e1 , . . . , eℓ } (ℓ ≥ 1) とおく． Si = (X ∩ Y ) ∪ {e1 , . . . , ei }, Ti = X ∪ {e1 , . . . , ei } Y e1 e2 e3 (i = 1, . . . , ℓ) とする．また，S0 = X ∩ Y , T0 = X と定義する． 14 / 33

証明の続き [ ⇐= ] 任意の X, Y ⊆ V を取る．Y
\ X = ∅ の場合は自明なので， X Y \ X ̸= ∅ と仮定して良い．Y \ X = {e1 , . . . , eℓ } (ℓ ≥ 1) とおく． Si = (X ∩ Y ) ∪ {e1 , . . . , ei }, Ti = X ∪ {e1 , . . . , ei } Y e1 e2 e3 (i = 1, . . . , ℓ) とする．また，S0 = X ∩ Y , T0 = X と定義する．このとき，Si−1 ⊆ Ti−1 , ei ∈ / Ti−1 (∀i) である．限界効用逓減性より f (Si−1 ∪ ei ) − f (Si−1 ) ≥ f (Ti−1 ∪ ei ) − f (Ti−1 ) (i = 1, . . . , ℓ) この式を i に対して足し上げると f (Sℓ ) − f (S0 ) ≥ f (Tℓ ) − f (T0 ). Sℓ = Y , S0 = X ∩ Y , Tℓ = X ∪ Y , T0 = X なので，劣モジュラ性が得られる． 14 / 33

劣モジュラ関数最小化 f : 2V → R 劣モジュラ関数, f (∅) =
0 劣モジュラ関数最小化 minimize f (X) subject to X ⊆ V 15 / 33

0 劣モジュラ関数最小化 minimize f (X) subject to X ⊆ V 例: • Kőnig–Egerváry: max M : マッチング • 最大流最小カット定理: • 独立マッチング: |M | = min+ |V + \ X| + |Γ(X)| max X⊆V φ:s–t フロー max M : 独立マッチング val(φ) = min s∈X⊆V −t u(Out(X)) |M | = min+ r+ (V + \ X) + r− (Γ(X)) X⊆V 15 / 33

0 劣モジュラ関数最小化 minimize f (X) subject to X ⊆ V アルゴリズム組合せ的なもの・連続最適化によるものなど様々な技法がある • Grötschel–Lovász–Schrijver (1981): Lovász 拡張 + 楕円体法 • 岩田–Fleischer–藤重 (2000, 2001), Schrijver (2000): 組合せ的 • Lee–Sidford–Wong (2015): 切除平面法 15 / 33

基多面体定義 P (f ) := {x ∈ RV :
x(X) ≤ f (X) (∀X ⊆ V )} B(f ) := {x ∈ P (f ) : x(V ) = f (V )} 劣モジュラ多面体劣モジュラ基多面体 cf. マトロイド多面体・基多面体（第 7 回） P (M) := {x ∈ RE + : x(X) ≤ r(X) (∀X ⊆ E)} B(M) := {x ∈ P (M) : x(E) = r(E)} 17 / 33

基多面体上の線形最適化 w ∈ RV maximize w⊤ x subject to x
∈ B(f ) 18 / 33

∈ B(f ) 貪欲法 1: V の要素を w の降順に並べる: w(v1 ) ≥ · · · ≥ w(vn ) (n = |V |). 2: x ∈ RV を次のように定める: x(vi ) := f (vi | {v1 , . . . , vi−1 }) (i = 1, . . . , n) マトロイドの最小重み基に対する貪欲法（第 7 回）の一般化 18 / 33

∈ B(f ) 貪欲法 1: V の要素を w の降順に並べる: w(v1 ) ≥ · · · ≥ w(vn ) (n = |V |). 2: x ∈ RV を次のように定める: x(vi ) := f (vi | {v1 , . . . , vi−1 }) (i = 1, . . . , n) マトロイドの最小重み基に対する貪欲法（第 7 回）の一般化定理貪欲法における x は基多面体上の線形最適化の最適解である． 18 / 33

定理の証明 (1/3) [x ∈ B(f ) であること] まず，∀X ⊆ V
に対し，x(X) ≤ f (X) を示す． x(X) = ∑ f (vi | {v1 , . . . , vi−1 }) i:vi ∈X ≤ ∑ f (vi | {v1 , . . . , vi−1 } ∩ X) i:vi ∈X = f (X) − f (∅) = f (X) また，定義から x(V ) = n ∑ f (vi | {v1 , . . . , vi−1 }) = f (V ) − f (∅) = f (V ). i=1 ∴ x ∈ B(f ). 19 / 33

定理の証明 (2/3) [x が最適であること] y ∈ B(f ) を任意に取る．w⊤ x
− w⊤ y ≥ 0 を示したい． ⊤ ⊤ w x−w y = n ∑ (x(vi ) − y(vi ))w(vi ) i=1 20 / 33

− w⊤ y ≥ 0 を示したい． ⊤ ⊤ w x−w y = n ∑ (x(vi ) − y(vi ))w(vi ) i=1 Abel 変形 n ∑ i=1 a i bi = S n b n − n−1 ∑ i=1 Si (bi+1 − bi ) ここで Si := ∑ aj j≤i 20 / 33

− w⊤ y ≥ 0 を示したい． ⊤ ⊤ w x−w y = n ∑ (x(vi ) − y(vi ))w(vi ) i=1 Abel 変形 n ∑ a i bi = S n b n − i=1 ⊤ n−1 ∑ Si (bi+1 − bi ) ここで Si := i=1 ⊤ w x − w y = Sn w(vn ) − ∑ aj j≤i n−1 ∑ Si (w(vi+1 ) − w(vi )) i=1 よって，Si ≥ 0 (i = 1, . . . , n − 1) を示せばよい． 20 / 33

定理の証明 (3/3) Claim. Si ≥ 0 (i = 1, .
. . , n − 1) (∵) Si = i ∑ (x(vj ) − y(vj )) j=1 = i ∑ f (vj | {v1 , . . . , vj−1 }) − y({v1 , . . . , vi }) j=1 = f ({v1 , . . . , vi }) − y({v1 , . . . , vi }) ≥ 0 (y ∈ B(f )) 21 / 33

Lovász 拡張定義 fˆ : RV → R, fˆ(w) :=
maxx∈B(f ) w⊤ x を Lovász 拡張という．貪欲法の解を代入すると， fˆ(w) = n ∑ w(vi )f (vi | {v1 , . . . , vi−1 }) i=1 = f (V )w(vn ) + n−1 ∑ f ({v1 , . . . , vi })(w(vi ) − w(vi+1 )) i=1 22 / 33

Lovász 拡張 fˆ(w) = f (V )w(vn ) + n−1
∑ f ({v1 , . . . , vi })(w(vi ) − w(vi+1 )) w i=1 特に w ∈ [0, 1]V に限ると，次式になる: fˆ(w) = θ E [f ({w ≥ θ})] θ∼[0,1] ここで， θ ∼ [0, 1] は一様分布に従う確率変数．また，略記 {w ≥ θ} := {v ∈ V : w(v) ≥ θ} v1 v2 v3 {w ≥ θ} を用いた． 23 / 33

Lovász 拡張の例 1.0 0.8 0.6 0.4 0.2 0.0 1.0 0.8
0.6 0.4 0.2 0.0 0.0 0.2 0.4 0.6 0.8 1.0 24 / 33

Lovász 拡張の性質定理 (Lovász 1983) 1 fˆ は凸関数． 2 fˆ(1X
) = f (X) (X ⊆ V ) 3 定理より，凸関数 fˆ の最小化で劣モジュラ関数 f の最小化ができる． −→ 楕円体法 [GLS81] min fˆ(w) = min f (X) w∈[0,1]V X⊆X 25 / 33

Lovász 拡張の性質定理 (Lovász 1983) 1 fˆ は凸関数． 2 fˆ(1X
) = f (X) (X ⊆ V ) 3 定理より，凸関数 fˆ の最小化で劣モジュラ関数 f の最小化ができる． −→ 楕円体法 [GLS81] min fˆ(w) = min f (X) w∈[0,1]V X⊆X (証明) ① fˆ(w) = maxx∈B(f ) w⊤ x であり，一般に複数の線形関数の最大値は凸関数． ② 期待値の式から自明． ③ ②より左辺 ≤ 右辺．一方，w ∈ [0, 1]V に対し fˆ(w) = E[f (. . . )] ≥ 右辺. 25 / 33

最小ノルム点法パラメトリック劣モ最小化 min f (X) + α|X| (SFMα ) X⊆V
Wolfe のアルゴリズム (藤重–Wolfe 法) 実用上最速定理 L2 正則化 Lovász 拡張最小化 1 minV fˆ(w) + ∥w∥2 (P) 2 w∈R 等価 (w∗ = −x∗ ) 最小ノルム点 min ∥x∥2 x∈B(f ) 27 / 33

パラメトリック劣モジュラ最小化 min f (X) + α|X| X⊆V (SFMα ) パラメータ
α ∈ R は動く Claim. Aα : (SFMα ) の最適解とすると，α < β =⇒ Aα ⊇ Aβ . 28 / 33

L2 正則化 Lovász 拡張最小化 1 min fˆ(w) + ∥w∥2 2
w∈RV (P) Aα : (SFMα ) の最適解．定理 w ∈ RV を w(v) := sup{α : v ∈ Aα } と定めると，w は (P) の一意な最適解である． 29 / 33

L2 正則化 Lovász 拡張最小化 1 min fˆ(w) + ∥w∥2 2
w∈RV (P) Aα : (SFMα ) の最適解．定理 w ∈ RV を w(v) := sup{α : v ∈ Aα } と定めると，w は (P) の一意な最適解である．系: w∗ : (P) の（一意）最適解とする． • {w∗ ≥ α} は (SFMα ) の最適解全ての α に対し，(SFMα ) の最適解が得られる！ • 特に，α = 0 とすると，次が得られる: {w∗ ≥ 0} は劣モジュラ最小化 min f (X) の最適解 X⊆V 29 / 33

定理の証明 (1/2) Claim. ほとんどすべての α について Aα = {w ≥
α}. Claim. fˆ(w) + 12 ∥w∥2 ≤ fˆ(w′ ) + 12 ∥w′ ∥2 (∀w′ ∈ RV ) 30 / 33

定理の証明 (1/2) Claim. ほとんどすべての α について Aα = {w ≥
α}. (∵) w の定義から， • w(v) < α =⇒ v ∈ / Aα . ∴ Aα ⊆ {w ≥ α}. • w(v) > α =⇒ α < ∃β < w(v) s.t. v ∈ Aβ . Claim「α < β =⇒ Aα ⊇ Aβ 」より，v ∈ Aα . ∴ {w > α} ⊆ Aα . よって，{w > α} ⊆ Aα ⊆ {w ≥ α} が成り立つ． Claim. fˆ(w) + 12 ∥w∥2 ≤ fˆ(w′ ) + 12 ∥w′ ∥2 (∀w′ ∈ RV ) 30 / 33

定理の証明 (2/2) (∵) 任意の w′ ∈ RV に対し，β < 0
を十分小さく取ると， 1 fˆ(w) + ∥w∥2 = 2 ∑ [ ∫ w(v) ∫ +∞ 1 f ({w ≥ α})dα + βf (V ) + αdα + β 2 2 β β v∈V ] ∫ +∞ [ ∑ = const. + f ({w ≥ α}) + α1w(v)≥α dα β ∫ +∞ [ = const. + β ∫ +∞ [ ≤ const. + ] v∈V ] f (Aα ) + α|Aα | dα (Aα = {w ≥ α} a.e.) ] f ({w′ ≥ α}) + α|{w′ ≥ α}| dα (Aα は [...] の最小解) β 1 = fˆ(w′ ) + ∥w′ ∥2 2 31 / 33

最小ノルム点補題 1 1 min fˆ(w) + ∥w∥2 = −
min ∥x∥2 2 2 x∈B(f ) w∈RV 特に，それぞれの（一意）最適解 w∗ , x∗ に対し w∗ = −x∗ が成り立つ． 32 / 33

最小ノルム点補題 1 1 min fˆ(w) + ∥w∥2 = −
min ∥x∥2 2 2 x∈B(f ) w∈RV 特に，それぞれの（一意）最適解 w∗ , x∗ に対し w∗ = −x∗ が成り立つ． (証明) 凸解析における minimax 定理を使う: X ⊂ Rn , Y ⊂ Rm : コンパクト凸集合 f : X × Y → R: x について凸関数, y について凹関数 min max f (x, y) = max min f (x, y) x∈X y∈Y y∈Y x∈X (詳細はレポート問題) 32 / 33

まとめ: 劣モジュラ最小化まとめ • 劣モジュラ関数，基多面体，Lovász 拡張の定義 • 最小ノルム点法とパラメトリック劣モジュラ最小化参考文献 •
河原・永野『劣モジュラ最適化と機械学習』 (2015) • F. Bach “Learning with Submodular Functions: A Convex Optimization Perspective” (2013) 33 / 33

組合せ最適化特論第 10 回（劣モジュラ最大化）担当: 相馬輔 2026/7/16 1 /
36

目次 1. 劣モジュラ最大化・定式化・モデリング例 2. 貪欲法・
古典貪欲法・連続貪欲法 2 / 36

単調劣モジュラ関数最大化 [Nemhauser, Wolsey, and Fisher 1978] f : 2V →
R+ ... 非負単調劣モジュラ, f (∅) = 0 def [単調 ⇐⇒ f (X) ≤ f (Y ) max f (X) s.t. (X ⊆ Y )] X∈C 4 / 36

R+ ... 非負単調劣モジュラ, f (∅) = 0 def [単調 ⇐⇒ f (X) ≤ f (Y ) max f (X) s.t. |X| ≤ k , (X ⊆ Y )] X∈C P i∈X w(i) ≤ 1 など 4 / 36

R+ ... 非負単調劣モジュラ, f (∅) = 0 def [単調 ⇐⇒ f (X) ≤ f (Y ) max f (X) s.t. |X| ≤ k , (X ⊆ Y )] X∈C P i∈X w(i) ≤ 1 など応用: • 文書要約 [Lin and Bilmes 2011] • モデル解釈 [Ribeiro, Singh, and Guestrin 2016] • 変数選択 [Das and Kempe 2011; Elenberg et al. 2018] 4 / 36

単調劣モジュラ最大化名前制約近似比 |X| ≤ k 1 − 1/e
[NWF ’78] P ナップサック制約 i∈X wi ≤ 1 1 − 1/e [Sviridenko 2004] サイズ制約マトロイド制約 X∈I 1 − 1/e [Calinescu et al. 2011] • (1 − 1/e) 近似 ⇐⇒ f (X) ≥ (1 − 1/e) maxX ∗ ∈C f (X ∗ ) となる X を出力 • 近似比 1 − 1/e はオラクルモデルの多項式時間アルゴリズムの中で最良 [Nemhauser and Wolsey 1978] 5 / 36

例: 最大被覆問題最大被覆問題入力 V : 基地局候補地の集合, k ∈ Z+
出力 S ⊆ V で |S| ≤ k かつ S に設置したときの被覆範囲が最大となるもの 6 / 36

例: 不可分財の分配 U = {v1 , . . . ,
vn } ... 財の集合 fi ... i さんの効用関数，単調劣モ (i = 1, . . . , m) Pm 社会効用 i=1 fi (Xi ) が最大の分配 (X1 , . . . , Xm ) を求めたい． f1 f2 f3 7 / 36

例: 不可分財の分配 • V := U の m 個のコピー P
• f (X) := m i=1 fi (X ∩ Ui ) • C : V 上の分割マトロイド（各財は 1 人まで割当可能）分割マトロイド制約の単調劣モ最大化 U1 U2 U3 8 / 36

例: 文書要約 [Lin and Bilmes 2011] V : 元文書の文全ての集合, X
⊆ V ←→ 要約 r1 , . . . , rK : 参照文 ce (X) = n-gram e が要約 X に現れる回数 Me,i = n-gram e が参照文 ri に現れる回数要約文民間英語試験の延期を決定した． ROUGE-N f (X) = X X 参照文 A min{ce (X), Me,i } r∈R e: 文 r に含まれる n-gram (※ 簡単のため正規化定数は省いた) 英語教育が専門の〇〇氏は，民間英語試験は問題が多く，... • ROUGE-N は単調劣モジュラ関数 • サイズ制約 ←→ 要約に使える文の数に制約 • ナップサック制約 ←→ 要約の文字数に制約 9 / 36

例: モデル解釈 (SP-LIME) [Ribeiro, Singh, and Guestrin 2016] 近年の機械学習モデルは複雑で解釈しづらい．→解釈性 Local
Iterpretable Model-agnostic Explanations (LIME) 各訓練データに対して，特徴量ごとの予測への貢献度を計算してくれる手法引用: LIME のチュートリアルデータセット全体での挙動を知りたい場合は？ 10 / 36

例: モデル解釈 (SP-LIME) [Ribeiro, Singh, and Guestrin 2016] V =
訓練データの集合 U = 特徴量の集合 aij = データ i に対する特徴量 j の LIME スコア G = (V, U ; E) ... aij > 0 の (i, j) に枝を引いた二部グラフ pP wj := i∈V aij ... 特徴量 j の重み f (X) = X X Γ(X) wj j∈ΓG (X) • モデルの全体的挙動を理解する上で多様な訓練データを抽出できる • サイズ制約 ←→ 抽出するデータ数に制約 11 / 36

例: 変数選択 [Das and Kempe 2011; Elenberg et al. 2018]
V = {1, . . . , n} xi : 説明変数 (i = 1, . . . , n), y : 被説明変数 f (X) = ∥y∥22 − min β:supp(β)⊆X y− n X i=1 2 βi xi 2 ... X に入っている変数だけ使ったときの最良残差 • 抑圧変数がない =⇒ f : 単調劣モジュラ • X = [x1 . . . xn ] に対する RIP 仮定 =⇒ f : 弱劣モジュラ（近似的に劣モジュラ） 12 / 36

最大化アルゴリズムサイズ制約 |X| ≤ k （組合せ的アルゴリズム） • 古典貪欲法 [Nemhauser, Wolsey,
and Fisher 1978] • 確率的貪欲法 [Mirzasoleiman et al. 2015] 一般の制約 X ∈ C （連続最適化的アルゴリズム） • 連続貪欲法 [Calinescu et al. 2011; Chekuri, Vondrák, and Zenklusen 2010; Chekuri, Vondrák, and Zenklusen 2014] 14 / 36

古典貪欲法 [Nemhauser, Wolsey, and Fisher 1978] 1: X0 ← ∅
2: for i = 1, . . . , k : 3: a ∈ V \ Xi−1 のうち f (Xi−1 ∪ a) が最大のものを求め，ai とする． 4: Xi ← Xi−1 ∪ ai 5: return X = Xk 15 / 36

2: for i = 1, . . . , k : 3: a ∈ V \ Xi−1 のうち f (Xi−1 ∪ a) が最大のものを求め，ai とする． 4: Xi ← Xi−1 ∪ ai 5: return X = Xk • 貪欲アルゴリズムの出力を X とすると， f (X) ≥ (1 − 1/e) max X ∗ :|X ∗ |=k f (X ∗ ) 最適値 15 / 36

古典貪欲法の解析補題 f : 劣モジュラ X [f (X ∪ a)
− f (X)] f (X ∪ Y ) ≤ f (X) + a∈Y \X 16 / 36

X0 = ∅ Xi = Xi−1 ∪ ai ai ∈
argmaxa∈V \Xi−1 f (Xi−1 ∪ a) 古典貪欲法の解析補題 f : 劣モジュラ X [f (X ∪ a) − f (X)] f (X ∪ Y ) ≤ f (X) + a∈Y \X 補題各 i = 1, 2, . . . , k に対して 1 f (Xi ) − f (Xi−1 ) ≥ [f (X ∗ ) − f (Xi−1 )] k X ∗ : 最適解 16 / 36

古典貪欲法の解析補題 f : 劣モジュラ X [f (X ∪ a)
− f (X)] f (X ∪ Y ) ≤ f (X) + a∈Y \X 補題各 i = 1, 2, . . . , k に対して 1 f (Xi ) − f (Xi−1 ) ≥ [f (X ∗ ) − f (Xi−1 )] k X ∗ : 最適解補題各 i = 0, 1, 2, . . . , k に対して i 1 ∗ f (X ) − f (Xi ) ≤ 1 − f (X ∗ ) k 16 / 36

古典貪欲法の解析補題定理 f : 劣モジュラ X [f (X ∪
a) − f (X)] f (X ∪ Y ) ≤ f (X) + f (Xk ) ≥ (1 − 1/e)f (X ∗ ) a∈Y \X 補題各 i = 1, 2, . . . , k に対して 1 f (Xi ) − f (Xi−1 ) ≥ [f (X ∗ ) − f (Xi−1 )] k X ∗ : 最適解補題各 i = 0, 1, 2, . . . , k に対して i 1 ∗ f (X ) − f (Xi ) ≤ 1 − f (X ∗ ) k 16 / 36

2: for i = 1, . . . , k : 3: a ∈ V \ Xi−1 のうち f (Xi−1 ∪ a) が最大のものを求め，ai とする． 4: Xi ← Xi−1 ∪ ai 5: return X = Xk • 貪欲アルゴリズムの出力を X とすると， f (X) ≥ (1 − 1/e) max X ∗ :|X ∗ |=k f (X ∗ ) 最適値 • O(nk) 回の f の関数値評価が必要 (n = |V |, k : サイズ制約) → 応用によっては重すぎる 17 / 36

確率的貪欲法 [Mirzasoleiman et al. 2015] ε > 0 を固定． X0
← ∅ 2: for i = 1, . . . , k : 3: Ri := V \ Xi−1 から nk log 1ε 個ランダムサンプル 4: ai ∈ argmaxa∈Ri f (Xi−1 ∪ a) 5: Xi ← Xi−1 ∪ ai 6: return X = Xk 1: 18 / 36

確率的貪欲法 [Mirzasoleiman et al. 2015] ε > 0 を固定． X0
← ∅ 2: for i = 1, . . . , k : 3: Ri := V \ Xi−1 から nk log 1ε 個ランダムサンプル 4: ai ∈ argmaxa∈Ri f (Xi−1 ∪ a) 5: Xi ← Xi−1 ∪ ai 6: return X = Xk 1: • E[f (X)] ≥ (1 − 1/e − ε)f (X ∗ ) • O(n log(1/ε)) 回の関数値評価古典貪欲法の O(nk) に比べて改善！ 18 / 36

最大化アルゴリズムサイズ制約 |X| ≤ k （組合せ的アルゴリズム） • 古典貪欲法 [Nemhauser, Wolsey,
and Fisher 1978] • 確率的貪欲法 [Mirzasoleiman et al. 2015] 一般の制約 X ∈ C （連続最適化的アルゴリズム） • 連続貪欲法 [Calinescu et al. 2011; Chekuri, Vondrák, and Zenklusen 2010; Chekuri, Vondrák, and Zenklusen 2014] 19 / 36

連続貪欲法 [Calinescu et al. 2011] 元問題 max {f (X) :
X ∈ C}

連続貪欲法 [Calinescu et al. 2011] ①連続緩和元問題緩和問題 max {f
(X) : X ∈ C} max {F (x) : x ∈ P }

(X) : X ∈ C} max {F (x) : x ∈ P } ②連続貪欲法 x∈P s.t. F (x) ≥ (1 − 1/e)f (X ∗ ) X ∗ : 最適解

(X) : X ∈ C} max {F (x) : x ∈ P } ②連続貪欲法 X∈C s.t. x∈P ∗ f (X) ≥ (1 − 1/e)f (X ) ③丸め s.t. F (x) ≥ (1 − 1/e)f (X ∗ ) X ∗ : 最適解 20 / 36

多重線形拡張 (multilinear extension) f の多重線形拡張 F : [0, 1]n →
R X Y Y F (x) := f (S) xi (1 − xi ) S⊆V i∈S i̸∈S = E[f (R(x))] R(x): 要素 i を確率 xi で独立に含むランダム集合注 F , ∇F は任意の精度で近似的に求められる (サンプリング)．以下，簡単のため F , ∇F を与えるオラクルがあるものとする． 22 / 36

多重線形拡張 (multilinear extension) 性質 • F (1X ) = f
(X) • f : 単調 =⇒ ∇F ≥ 0 2 F • f : 劣モ =⇒ ∂x∂ ∂x ≤ 0 (i ̸= j ) i j 特に F は非負方向に凹, ei − ej 方向に凸 1.0 0.8 0.6 0.4 0.2 0.0 1.0 0.8 0.6 0.4 0.2 0.0 0.0 0.2 0.4 0.6 0.8 1.0 ※一般には凸でも凹でもない 23 / 36

多重線型拡張の性質補題 f : 単調 =⇒ ∇F ≥ 0 (証明)
i ∈ V を任意に取る．∇F (x)i を計算してみると ∇F (x)i = X X⊆V \i f (X ∪ i) Pr(X) − X f (X) Pr(X). X⊆V \i Q Q ここで，Pr(X) = k∈X xk k∈X:k̸ / =i (1 − xk ) である．f の単調性より f (X ∪ i) − f (X) ≥ 0 なので，∇F (x)i ≥ 0. 24 / 36

多重線型拡張の性質補題 2 F f : 劣モ =⇒ ∂x∂i ∂x
≤ 0 (i ̸= j ) j 特に φ(t) = F (x + td) (d ≥ 0) は凹関数，ψ(t) = F (x + t(ei − ej )) は凸関数 2 F = 0. i ̸= j のとき， (証明) i = j の場合は自明に ∂x∂i ∂x j ∂ 2F (x) = ∂xi ∂xj X [f (X ∪ i ∪ j) + f (X) − f (X ∪ i) − f (X ∪ j)] Pr(X). X⊆V \{i,j} Q x k k∈X k∈X:k̸ / =i,j (1 − xk ) である．劣モジュラ性より 2F (x) ≤ 0. f (X ∪ i ∪ j) + f (X) − f (X ∪ i) − f (X ∪ j) ≤ 0 なので ∂x∂i ∂x j ここで，Pr(X) = Q 25 / 36

≤ 0 (i ̸= j ) j 特に φ(t) = F (x + tv) (v ≥ 0) は凹関数，ψ(t) = F (x + t(ei − ej )) は凸関数 (証明) 連鎖律より φ′′ (t) = X ∂ 2F (x + tv)vi vj ∂xi ∂xj i,j∈V F であるが， ∂x∂i ∂x (x + tv) ≤ 0 で，仮定より vi , vj ≥ 0 であるから，φ′′ (t) ≤ 0. よっ j 2 て φ は凹関数． 26 / 36

≤ 0 (i ̸= j ) j 特に φ(t) = F (x + tv) (v ≥ 0) は凹関数，ψ(t) = F (x + t(ei − ej )) は凸関数 (証明) 連鎖律より φ′′ (t) = X ∂ 2F (x + tv)vi vj ∂xi ∂xj i,j∈V F であるが， ∂x∂i ∂x (x + tv) ≤ 0 で，仮定より vi , vj ≥ 0 であるから，φ′′ (t) ≤ 0. よっ j 2 て φ は凹関数．再び連鎖律より ψ ′′ (t) = −2 ∂ 2F (x + t(ei − ej )) ≥ 0 ∂xi ∂xj 26 / 36

連続貪欲法 (連続時間版) 連続緩和問題 max F (x) s.t. x ∈ P
28 / 36

以下の微分方程式に従って x(t) を動かす x(0) = 0 dx(t) = argmaxv∈P ∇F (x(t))⊤ v dt x(1) v(t) x(t) x(0) 28 / 36

以下の微分方程式に従って x(t) を動かす x(0) = 0 dx(t) = argmaxv∈P ∇F (x(t))⊤ v dt x(1) v(t) 定理 ([Calinescu et al. 2011]) f : 単調劣モ, P : down closed =⇒ x(1) ∈ P かつ F (x(1)) ≥ (1 − 1/e) maxx∗ ∈P F (x∗ ) x(t) x(0) 28 / 36

定理の証明 Ψ(t) := et−1 F (x(t)) とする. dΨ = et−1
[F (x(t)) + ∇F (x(t))⊤ dx(t) ]. dt dt x∗ ∈ P を最適解, x∗ ∨ x(t) を x∗ と x(t) の成分ごとに max をとったベクトルとする. x(t) ∨ x∗ x∗ F (x∗ ) ≤ F (x∗ ∨ x(t)) ≤ F (x(t)) + ∇F (x(t))⊤ (x∗ ∨ x(t) − x(t)) この上で凹 ⊤ ≤ F (x(t)) + ∇F (x(t)) v(t) dx(t) = F (x(t)) + ∇F (x(t))⊤ dt x(t) ∴ dΨ ≥ et−1 F (x∗ ). dt [0, 1] で積分: Ψ(1) − Ψ(0) = F (x(1)) ≥ (1 − e−1 )F (x∗ ). 29 / 36

連続貪欲法 (離散時間版) 実際には微分方程式を厳密に解くことはできないので，時間を離散化して近似する x(0) = 0 2: for t
= 0, δ, 2δ, . . . , 1 − δ : 3: v(t) ∈ argmaxv∈P ∇F (x(t))⊤ v を求める 4: x(t + δ) ← x(t) + δv(t) 5: return x(1) 1: • Frank-Wolfe 法の亜種 • 精度 ε > 0 に応じて時間幅 δ を十分小さく取れば，同様の仮定のもと F (x) ≥ (1 − 1/e − ε) maxx∗ ∈P F (x∗ ) 30 / 36

丸めアルゴリズム連続貪欲法で得られる緩和解 x は {0, 1} ベクトルとは限らないので， {0, 1} ベクトルに丸める必要がある.
→制約ごとに丸めアルゴリズムを設計マトロイド制約 • Pipage Rounding [Calinescu et al. 2011] • Swap Rounding [Chekuri, Vondrák, and Zenklusen 2010] その他の制約 • Contention Resolution Scheme [Chekuri, Vondrák, and Zenklusen 2014] 32 / 36

Pipage Rounding 1 2 3 4 [Calinescu et al. 2011]
xi , xj が{0,1} でない i, j ∈ V を取る α+ = max{α ≥ 0 : x + α(ei − ej ) ∈ P } α− = max{α ≥ 0 : x − α(ei − ej ) ∈ P } x+ = x + α+ (ei − ej ), x− = x − α− (ei − ej ) のうち F の値が大きいものに x を更新 x+ α+ x α− x− P をぶつかった面に制限して 1 に戻る定理 P : マトロイド多面体のとき，Pipage Rounding の出力 x は {0, 1} ベクトルで， F (x) ≥ F (x) を満たす（x: Pipage Rounding の初期点） 33 / 36

劣モジュラ最大化: 発展的な話題整数格子点上の劣モジュラ最大化 • 最適予算配分問題 • 最大化アルゴリズム連続劣モジュラ関数 • 非凸連続最適化（連続
DR 劣モジュラ関数）オンライン劣モジュラ最大化 • 近似 no-regret アルゴリズム • 連続 DR 劣モジュラ関数の CVaR 最大化 1.0 0.8 0.6 0.4 0.2 0.0 1.0 0.8 0.6 0.4 0.2 0.0 0.0 0.2 0.4 0.6 0.8 1.0 34 / 36

参考文献 Calinescu, G., C. Chekuri, M. Pál, and J. Vondrák
(2011). “Maximizing a monotone submodular function subject to a matroid constraint”. In: SIAM Journal on Computing 40.6, pp. 1740–1766. Chekuri, C., J. Vondrák, and R. Zenklusen (2010). “Dependent randomized rounding via exchange properties of combinatorial structures”. In: Proceedings of IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS), pp. 575–584. — (2014). “Submodular function maximization via the multilinear relaxation and contention resolution schemes”. In: SIAM Journal on Computing 43.6, pp. 1831–1879. Das, A. and D. Kempe (2011). “Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection”. In: Proceedings of the 28th International Conference on Machine Learning (ICML), pp. 1057–1064. Elenberg, E. R., R. Khanna, A. G. Dimakis, and S. Negahban (2018). “Restricted strong convexity implies weak submodularity”. In: Annals of Statistics 46.6B, pp. 3539–3568. Lin, H. and J. Bilmes (2011). “A class of submodular functions for document summarization”. In: Proceedings of the Annual Conference of the North American Chapter of the Association for Computational Linguistics, pp. 510–520. Mirzasoleiman, B., A. Badanidiyuru, A. Karbasi, J. Vondrak, and A. Krause (2015). “Lazier than lazy greedy”. In: Proceedings of AAAI Conference on Artiﬁcial Intelligence (AAAI). Nemhauser, G. L. and L. A. Wolsey (1978). “Best Algorithms for Approximating the Maximum of a Submodular Set Function”. In: Mathematics of Operations Research 3.3, pp. 177–188. Nemhauser, G. L., L. A. Wolsey, and M. L. Fisher (1978). “An analysis of approximations for maximizing submodular set functions - II”. In: Mathematical Programming 8, pp. 73–87. Ribeiro, M. T., S. Singh, and C. Guestrin (2016). “"Why should i trust you?" Explaining the predictions of any classiﬁer”. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 1135–1144. 35 / 36

Sviridenko, M. (2004). “A note on maximizing a submodular set
function subject to a knapsack constraint”. In: Operations Research Letters 32.1, pp. 41–43. 36 / 36

組合せ最適化特論

組合せ最適化特論

More Decks by Tasuku Soma

Other Decks in Education

Featured

Transcript