First Course in Combinatorial Optimization

Presentation on theme: "First Course in Combinatorial Optimization"— Presentation transcript:

1 First Course in Combinatorial Optimization
Jan. 28, 2008

2 8. Optimizing Submodular Functions
8.1 Minimizing Submodular Functions 8.2 Minimizing Submodular Functions Over Odd Sets 8.3 Maximizing Submodular Functions

3 8.1 Minimize Submodular Functions
サブモジュラ関数 次の不等式を満たす，台集合Eの部分集合族上の関数 例: ランク関数 ⇒サブモジュラ性の証明は1.5節 サブモジュラ関数の最小化問題は多項式時間で解ける． 最小カット問題 マトロイドの最大共通独立集合の発見問題 などを(理論的には)多項式時間で解ける

4 Minimum-weight cuts 8 4 v 9 6 3 10 1 2 5 7 w

5 f(W)がサブモジュラ関数であることを示す
Minimum-weight cuts 8 4 v 9 6 3 10 1 2 5 7 w W+v f(W)がサブモジュラ関数であることを示す

6 Minimum-weight cuts G A B C6 v C1 C4 C2 C3 C7 w C5

7 Minimization Algorithm

8 Linear Relaxation ⇒具体的にどういうことか?

9 Linear Relaxation

10 Ellipsoid Method 楕円体法: f'(x)が凸関数であれば，[0,1]E上での最小値を多項式時間で求めることができる．

11 Solution in Lattice points

12 8.2 Minimizing Submodular Function Over Odd Sets
(T=Eとすれば，要素数が奇数である集合Sの中で最小値を求める) 最大重みマッチング問題などを解くことができる

13 Maximum-Weight Matching
8 4 9 6 3 10 1 2 5 7

14 Maximum-Weight Matching

15 Maximum-Weight Matching
S

16 Max-Weight Perfect Matching

17 Max-Weight Perfect Matching

18 Algorithm

19 (1) |T| odd odd even

20 (2) |T| even, |U∩T| odd

21 Calculate U e f

22 (3) |T| even, |U∩T| even

23 Computation Time

24 Correctness for odd submodular function

25 Correctness for odd submodular function
X* U

26 Correctness for odd submodular function
X* U

27 8.3 Maximizing Submodular Function
Submodular関数の最大化問題は，一般には多項式時間では解けない.ただし，Submodular関数によっては，多項式時間アルゴリズムが存在する問題もある. 多項式時間 最大マッチング問題 超多項式時間 ハミルトン閉路問題