First Course in Combinatorial Optimization Jan. 28, 2008
8. Optimizing Submodular Functions 8.1 Minimizing Submodular Functions 8.2 Minimizing Submodular Functions Over Odd Sets 8.3 Maximizing Submodular Functions
8.1 Minimize Submodular Functions サブモジュラ関数 次の不等式を満たす，台集合Eの部分集合族上の関数 例: ランク関数 ⇒サブモジュラ性の証明は1.5節 サブモジュラ関数の最小化問題は多項式時間で解ける． 最小カット問題 マトロイドの最大共通独立集合の発見問題 などを(理論的には)多項式時間で解ける
Minimum-weight cuts 8 4 v 9 6 3 10 1 2 5 7 w
f(W)がサブモジュラ関数であることを示す Minimum-weight cuts 8 4 v 9 6 3 10 1 2 5 7 w W+v f(W)がサブモジュラ関数であることを示す
Minimum-weight cuts G A B C6 v C1 C4 C2 C3 C7 w C5
Minimization Algorithm
Linear Relaxation ⇒具体的にどういうことか?
Linear Relaxation
Ellipsoid Method 楕円体法: f'(x)が凸関数であれば，[0,1]E上での最小値を多項式時間で求めることができる．
Solution in Lattice points
8.2 Minimizing Submodular Function Over Odd Sets (T=Eとすれば，要素数が奇数である集合Sの中で最小値を求める) 最大重みマッチング問題などを解くことができる
Maximum-Weight Matching 8 4 9 6 3 10 1 2 5 7
Maximum-Weight Matching
Maximum-Weight Matching S
Max-Weight Perfect Matching
Max-Weight Perfect Matching
Algorithm
(1) |T| odd odd even
(2) |T| even, |U∩T| odd
Calculate U e f
(3) |T| even, |U∩T| even
Computation Time
Correctness for odd submodular function
Correctness for odd submodular function X* U
Correctness for odd submodular function X* U
8.3 Maximizing Submodular Function Submodular関数の最大化問題は，一般には多項式時間では解けない.ただし，Submodular関数によっては，多項式時間アルゴリズムが存在する問題もある. 多項式時間 最大マッチング問題 超多項式時間 ハミルトン閉路問題