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

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

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

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

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 を見つけるアルゴリズムが存在する

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

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

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) の大きい方を返す

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

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

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

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

線形代数 定理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>

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

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

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

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

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

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

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

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

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) の大きい方を返す

アルゴリズムの解析 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

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