Max Cut and the Smallest Eigenvalue 論文紹介

Presentation on theme: "Max Cut and the Smallest Eigenvalue 論文紹介"— Presentation transcript:

1 Max Cut and the Smallest Eigenvalue 論文紹介
京都大学情報学研究科 川原　純 Greatest Hits 2009 輪講

2 Luca Trevisan, Max Cut and the Smallest Eigenvalue, STOC 2009
3 1 3 4 カット（の利得）は = 28 6 5 最大カットを求める問題 8 2 3 7 Luca Trevisan, Max Cut and the Smallest Eigenvalue, STOC 2009 Theorem 5 Recursive-Spectral-Cut の近似率は － δ

3 既存研究 SDP を用いた近似率 0.878 のアルゴリズム [Goemans and Williamson 95]
→ 頂点数が多い場合は苦しい → 今回の近似率 のアルゴリズム

4 Max Cut の自明なアルゴリズム 以下、すべて Randomized アルゴリズムの話とする 3 アルゴリズムのカット 1 近似率 =
4 ≦ 1 最適カット 6 5 8 2 3 7 各頂点について、確率 1/2 で左に入れるか右に入れるかを決める 各枝について、 枝の端が片方ずつに含まれる確率は1/2 したがって、1/2の確率でその枝は カットになる 近似率 = 1/2 cut(G) = |E|/2

5 Theorem 1 Theorem 1 (Main) input
グラフ G = (V, E), G のMax CUT のOPT は (1 – ε) |E| 枝 (i, j) の重み Ai,j 頂点 i の重みつき次数 di パラメータ δ 1 3 4 1 A12 = 3 3 4 - 1 6 5 5 d1 = 3+3+4 2 1 8 2 3 このとき、 6 3 7 - 1 1 を満たすベクトル y ∈ {-1, 0, 1}V を見つけるアルゴリズムが存在する

6 Theorem 1 の式の意味 Theorem 1 (Main) input
グラフ G = (V, E), G のMax CUT のOPT は (1 – ε) |E| 枝 (i, j) の重み Ai,j 頂点 i の重みつき次数 di パラメータ δ 1 4 3 C + U + X = M C: カットした枝の本数 U: カットされない枝の本数 X: 片端だけが L∪R に接続している枝の数 M: 少なくとも片端が L∪R に接続している枝の数 3 4 1 - 1 6 5 5 2 1 8 2 3 （枝 (1, 4) 以外のすべての枝） 6 3 7 - 1 1

7 Theorem 1 の式の意味 Theorem 1 (Main) input
2 ( 2 U + X ) Theorem 1 の式の意味 ≦ 4 √ε + δ 2 C + 2U + X 2 ( 2 U + X ) ≦(4 √ε + δ) (2 C + 2U + X) ≦(4 √ε + δ) (2 C + 2U + 2X) Theorem 1 (Main) U + X/2 ≦(2 √ε + δ/2) (C + U + X) = M input グラフ G = (V, E), G のMax CUT のOPT は (1 – ε) |E| M – (2 √ε + δ/2) M ≦ M – U – X/2 枝 (i, j) の重み Ai,j 頂点 i の重みつき次数 di (1 – 2 √ε – δ/2) M ≦ C + X/2 パラメータ δ 1 – 2 √ε – δ/2 ≦ (C + X/2) / M 2 ( 2 U + X ) 1 4 2 C + 2U + X 3 C + U + X = M 1 C: カットした枝の本数 U: カットされない枝の本数 X: 片端だけが L∪R に接続している枝の数 M: 少なくとも片端が L∪R に接続している枝の数 3 4 - 1 6 5 5 2 1 8 2 3 （枝 (1, 4) 以外のすべての枝） 7 6 3 - 1 1

8 Theorem 1 を利用した Max Cut アルゴリズム
1 – 2 √ε – δ/2 ≦ (C + X/2) / M アルゴリズム Recursive-Spectral-Cut input: グラフ G = (V, E), 正確さパラメータ δ V’ Theorem 1 のアルゴリズムを走らせてカットを得る。 C: カットした枝の本数 U: カットされない枝の本数 X: 片端だけが L∪R に接続している枝の数 M: 少なくとも片端が L∪R に接続している枝の数 L R if C + X/2 ≦ M/2 自明なアルゴリズムでグラフをカットして返す V1 V2 if C + X/2 > M/2 L R V’ について再帰的にRecursive-Spectral-Cut を呼び出す (V1 ∪L, V2 ∪R) と (V1 ∪R, V2 ∪ L) の大きい方を返す

9 Theorem 1 の証明(1) Lemma 2 G の隣接行列を A、次数行列を D とする。このとき、
以下の式を満たすベクトル x ∈ RV が存在する 以下の式を満たすベクトル x ∈ RV を計算する 　　　　　　　　　　　　　　　　　時間アルゴリズムが存在する 0.02 0.31 1 3 4 1 3 4 - 1.52 6 5 D = 5 A = 2 1.28 8 2 3 3 7 6 - 3.18 対称行列 1.93 対角行列

10 Theorem 1 の証明(2) Lemma 3 G の隣接行列を A、次数行列を D とする。
ベクトル x ∈ RV が存在し、以下を満たすとする。 cf ) Lemma 2 の式 このとき、 を満たすベクトル y ∈ {-1, 0, 1}V を見つけるアルゴリズムが存在する Lemma 2 と Lemma 3 を合わせると Theorem 1 が言える

11 Lemma 2 の証明 以下の最小化問題を考える G の最適なカットを考える ≦ 2 ( ε – ( 1 – ε ) ) |E|
( x1* Lemma 2 の証明 を満たすx の存在を証明 x2* Aij: 隣接行列 D: 次数行列 … D = (x1* x2* ) … 以下の最小化問題を考える ( ( x1* x2* … =(x1* x2* ) … G の最適なカットを考える ( = Σ Aij xi* xj* i,j = 2 (cut されない辺 ― cut される辺) ≦ 2 ( ε – ( 1 – ε ) ) |E| xi* = -1 xi* = 1 とする = 2 ( 2 ε - 1) |E| ^ 最適解を x とすると

12 Theorem 1 の証明 Lemma 2 G の隣接行列を A、次数行列を D とする。このとき、
以下の式を満たすベクトル x ∈ RV が存在する 証明終 以下の式を満たすベクトル x ∈ RV を計算する 　　　　　　　　　　　　　　　　　時間アルゴリズムが存在する

13 線形代数 定理0.1 A をn次正方対称行列とする。A の最大の固有値をα、 最小の固有値を β とする。このとき
<Ax, x> α = sup <x, y> は x と y の内積 x <x, x> x はn次元実ベクトル cf) <Ax, x> β = inf <x, x> x 略証　　A の固有値を α1,…,αn とし（α1が最大）、対応する長さ1の 固有ベクトルを e1,…,en とする。 Ae1 =α1 e1 x = x1 e1 + x2e2 + …+ xn en　に対し Ax = x1 α1e1 + x2α2e2 + …+ xn αn en 一方、 <Ae1, e1> <Ax, x> = α1|x1|2 + α2|x2|2 + …+ αn|xn|2 = α1 = α <e1, e1> ≦ α( |x1|2 + |x2|2 + …+ |xn|2) = α <x, x>

14 を満たす実ベクトルx を 時間で見つけるアルゴリズムが存在[KW92] I – D-1/2AD1/2 の最大固有値は少なくとも 1 – (2ε – 1) = 2 – 2ε を満たす実ベクトルx’ を 見つけることができる とすると

15 Lemma 3 の証明 Lemma 3 （再掲） G の隣接行列を A、次数行列を D とする。
ベクトル x ∈ RV が存在し、以下を満たすとする。 cf ) Lemma 2 の式 このとき、 を満たすベクトル y ∈ {-1, 0, 1}V を見つけるアルゴリズムが存在する を変形すると

16 Lemma 3 の証明 以下ではこの値が√8ε 以下に なることを示す Algorithm 2TSC
を満たすyが存在 Algorithm 2TSC 各k について、ベクトル yk ∈ {-1, 0, 1}V を以下のように定義 以下の値の最小値を出力 0.02 0.31 1 3 4 1 3 4 - 1.52 6 5 5 2 1.28 8 2 3 6 3 7 - 3.18 1.93

17 Lemma 3 の証明 以下ではこの値が√8ε 以下に なることを示す Algorithm 2TSC
を満たすyが存在 Algorithm 2TSC 各k について、ベクトル yk ∈ {-1, 0, 1}V を以下のように定義 k = 1 しきい値 0.02 k = 2 しきい値 1.52 1 1 -1 以下の値の最小値を出力 1 1 -1 -1 k = 3 しきい値 3.18 k = 4 しきい値 0.31 0.02 0.31 1 -1 1 3 4 1 1 -1 3 4 ラウンディング k = 5 しきい値 1.28 k = 6 しきい値 1.93 - 1.52 6 5 5 2 1.28 8 2 3 6 -1 3 7 - 3.18 1.93 -1 1 -1

18 t を [0, max i xi2] から一様ランダムに取得
Y ∈ {-1, 0, 1}V を以下のように定める もし 2TSC が以下の条件を満たす y を出力するなら 確率1で以下の式が成り立つ 特に したがって、以下の式が示されれば Lemma 3 が示される

19 以下では と仮定する 以下の式が成り立つことを示す として一般性を失わない (1) xi と xj の符号が異なるとき =
以下では　　　　　　　　　と仮定する 以下の式が成り立つことを示す として一般性を失わない (1) xi と xj の符号が異なるとき それ以外 = (2) xi と xj の符号が同じとき = したがって

20 また が成り立つ コーシー・シュワルツの不等式

21 問題の仮定より が成り立つので したがって が成り立つ

22 Theorem 1 を利用した Max Cut アルゴリズム（再掲）
アルゴリズム Recursive-Spectral-Cut input: グラフ G = (V, E), 正確さパラメータ δ V’ Theorem 1 のアルゴリズムを走らせてカットを得る。 C: カットした枝の本数 U: カットされない枝の本数 X: 片端だけが L∪R に接続している枝の数 M: 少なくとも片端が L∪R に接続している枝の数 L R if C + X/2 ≦ M/2 自明なアルゴリズムでグラフをカットして返す V1 V2 if C + X/2 > M/2 L R V’ について再帰的にRecursive-Spectral-Cut を呼び出す (V1 ∪L, V2 ∪R) と (V1 ∪R, V2 ∪ L) の大きい方を返す

23 アルゴリズムの解析 Theorem 4 ε < 1/16
アルゴリズム Recursive-Spectral-Cut は OPT が (1 – ε) |E| の グラフ G = (V, E) を受け取ると、少なくとも (1 – 4√ε + 8ε – δ/2) |E| のカットを返す。 証明 t 回目のループを考える Gt+1 ρt+1 |E| OPT は少なくとも(1- ε/ρt)|E| Gt Theorem 1 のアルゴリズムによって 少なくとも (1 – 2√ ε/ρt- δ/2 )|E|(ρt-ρt+1) はカット ρt|E| Lt Rt

24

25 Theorem 5 Recursive-Spectral-Cut の近似率は － δ 証明

26