kawahara_maxcut

Max Cut and the Smallest
Eigenvalue 論文紹介
京都大学情報学研究科
川原純
Greatest Hits 2009 輪講
• Max Cut の近似アルゴリズムを紹介
グラフ G
3
3
6
3
1
4
8
5
2
カット（の利得）は 3 + 4 + 6 + 8 + 7 = 28
最大カットを求める問題
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]
→ 頂点数が多い場合は苦しい
• SDP を用いない場合は自明な 0.5 より良い結果は無し
→ 今回の近似率 0.531 のアルゴリズム
Max Cut の自明なアルゴリズム
• 以下、すべて Randomized アルゴリズムの話とする
3
3
6
3
1
4
8
近似率 =
アルゴリズムのカット
最適カット
5
≦1
2
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
-1
2
3
このとき、
-1 3
0
3
0
4
4
1
6
8
5
5
2 1
7
6
A12 = 3
d1 = 3+3+4
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
パラメータ δ
0
1
3
-1
2
3
-1 3
0
3
4
4
1
6
8
5
5
2 1
7
6
1
C+U+X=M
C: カットした枝の本数
U: カットされない枝の本数
X: 片端だけが L∪R に接続している枝の数
M: 少なくとも片端が L∪R に接続している枝の数
（枝 (1, 4) 以外のすべての枝）
2(2U+X)
2 C + 2U + X
2(2U+X)
≦ 4 √ε + δ
Theorem 1 の式の意味
≦(4 √ε + δ) (2 C + 2U + X)
≦(4 √ε + δ) (2 C + 2U + 2X)
Theorem 1 (Main)
U + X/2 ≦(2 √ε + δ/2) (C + U + X)
input グラフ G = (V, E), MG–のMax
CUTMのOPT
(1 – ε) |E|= M
(2 √ε + δ/2)
≦ M – Uは
– X/2
枝 (i, j) の重み Ai,j(1 – 2 √ε
頂点
i の重みつき次数
di
– δ/2)
M ≦ C + X/2
1 – 2 √ε – δ/2 ≦ (C + X/2) / M
0
1
3
-1
2
3
-1 3
0
3
パラメータ δ
2(2U+X)
2 C + 2U + X
4
4
1
6
8
5
5
2 1
7
6
1
C+U+X=M
C: カットした枝の本数
U: カットされない枝の本数
X: 片端だけが L∪R に接続している枝の数
M: 少なくとも片端が L∪R に接続している枝の数
（枝 (1, 4) 以外のすべての枝）
Theorem 1 を利用した
Max Cut アルゴリズム
アルゴリズム Recursive-Spectral-Cut
1 – 2 √ε – δ/2 ≦ (C + X/2) / M
input: グラフ G = (V, E), 正確さパラメータ δ
V’
Theorem 1 のアルゴリズムを走らせてカットを得る。
C: カットした枝の本数
U: カットされない枝の本数
X: 片端だけが L∪R に接続している枝の数
M: 少なくとも片端が L∪R に接続している枝の数
L
if C + X/2 ≦ M/2
自明なアルゴリズムでグラフをカットして返す
V1
if C + X/2 > M/2
V’ について再帰的にRecursive-Spectral-Cut を呼び出す L
(V1 ∪L, V2 ∪R) と (V1 ∪R, V2 ∪ L) の大きい方を返す
R
V2
R
Theorem 1 の証明(1)
Lemma 2
G の隣接行列を A、次数行列を D とする。このとき、
以下の式を満たすベクトル x ∈ RV が存在する
以下の式を満たすベクトル x ∈ RV を計算する
時間アルゴリズムが存在する
0.02
1
3
- 1.52
2
3
- 3.18 3
1
4
6
3
0.31
4
8
7
5
5
A=
1.28
2
6
1.93
0
3
0
3
4
0
3
0
3
0
0
8
0
3
0
6
0
7
3
0
6
0
1
5
4
0
0
1
0
2
0
8
7
5
2
0
D=
対称行列
10 0 0 0 0 0
0 14 0 0 0 0
0 0 18 0 0 0
0 0 0 10 0 0
0 0 0 0 7 0
0 0 0 0 0 22
対角行列
Theorem 1 の証明(2)
Lemma 3
G の隣接行列を A、次数行列を D とする。
ベクトル x ∈ RV が存在し、以下を満たすとする。
cf ) Lemma 2 の式
このとき、
を満たすベクトル y ∈ {-1, 0, 1}V を見つけるアルゴリズムが存在する
Lemma 2 と Lemma 3 を合わせると Theorem 1 が言える
(
10 0 0 0 0 0
x1*
0 14 0 0 0 0
x2*
0 0 18 0 0 0
D = (x1* x2* … )
0 0 0 10 0 0
0 0 0 0 7 0
0 0 0 0 0 22
以下の最小化問題を考える
0
3
0
6
0
7
3
0
6
0
1
5
4
0
0
1
0
2
0
8
7
5
2
0
x1*
x2*
(
3
0
3
0
0
8
…
G の最適なカットを考える
0
3
0
=(x1* x2* …
)
3
4
0
= Σ Aij xi* xj*
i,j
(
(
…
Lemma 2 の証明
を満たすx の存在を証明
Aij: 隣接行列
D: 次数行列
= 2 (cut されない辺 ― cut される辺)
xi* = -1
xi* = 1 とする
最適解を ^x とすると
≦ 2 ( ε – ( 1 – ε ) ) |E|
= 2 ( 2 ε - 1) |E|
Theorem 1 の証明
Lemma 2
G の隣接行列を A、次数行列を D とする。このとき、
以下の式を満たすベクトル x ∈ RV が存在する
証明終
以下の式を満たすベクトル x ∈ RV を計算する
時間アルゴリズムが存在する
線形代数
定理0.1
A をn次正方対称行列とする。A の最大の固有値をα、
最小の固有値を β とする。このとき
α = sup <Ax, x>
<x, y> は x と y の内積
x
<x, x>
β = inf
x
<Ax, x>
<x, x>
x はn次元実ベクトル
cf)
略証 A の固有値を α1,…,αn とし（α1が最大）、対応する長さ1の
固有ベクトルを e1,…,en とする。
Ae1 =α1 e1
x = x1 e1 + x2e2 + …+ xn en に対し
Ax = x1 α1e1 + x2α2e2 + …+ xn αn en
<Ax, x> = α1|x1|2 + α2|x2|2 + …+ αn|xn|2
≦ α( |x1|2 + |x2|2 + …+ |xn|2) = α <x, x>
一方、
<Ae1, e1>
<e1, e1>
= α1 = α
を満たす実ベクトル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 を見つけるアルゴリズムが存在する
を変形すると
以下ではこの値が√8ε 以下に
なることを示す
Lemma 3 の証明
を満たすyが存在
Algorithm 2TSC
各k について、ベクトル yk ∈ {-1, 0, 1}V を以下のように定義
以下の値の最小値を出力
0.02
1
3
- 1.52
2
3
- 3.18 3
1
4
6
3
0.31
4
8
7
5
5
2 1.28
6
1.93
以下ではこの値が√8ε 以下に
なることを示す
Lemma 3 の証明
を満たすyが存在
Algorithm 2TSC
各k について、ベクトル yk ∈ {-1, 0, 1}V を以下のように定義
k = 1 しきい値 0.02 k = 2 しきい値 1.52
0
1
0
0
1
以下の値の最小値を出力
0
-1
-1
0
1
-1
1
k = 3 しきい値 3.18 k = 4 しきい値 0.31
0
0
0
0
0.02
1
3
- 1.52
2
3
3
- 3.18 3
1
4
6
8
7
0
0.31
4
5
ラウンディング
5
2 1.28
6
0
-1
0
1
0
-1
k = 5 しきい値 1.28 k = 6 しきい値 1.93
0
0
0
0
0
-1
1.93
1
-1
1
0
0
-1
0
t を [0, max i xi2] から一様ランダムに取得
Y ∈ {-1, 0, 1}V を以下のように定める
もし 2TSC が以下の条件を満たす y を出力するなら
確率1で以下の式が成り立つ
特に
したがって、以下の式が示されれば Lemma 3 が示される
以下では
と仮定する
以下の式が成り立つことを示す
として一般性を失わない
(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
if C + X/2 ≦ M/2
自明なアルゴリズムでグラフをカットして返す
V1
if C + X/2 > M/2
V’ について再帰的にRecursive-Spectral-Cut を呼び出す L
(V1 ∪L, V2 ∪R) と (V1 ∪R, V2 ∪ L) の大きい方を返す
R
V2
R
アルゴリズムの解析
ε < 1/16
Theorem 4
アルゴリズム Recursive-Spectral-Cut は OPT が (1 – ε) |E| の
グラフ G = (V, E) を受け取ると、少なくとも (1 – 4√ε + 8ε – δ/2) |E|
のカットを返す。
証明
t 回目のループを考える
ρt+1 |E|
Gt+1
Gt
Lt
Rt
OPT は少なくとも(1- ε/ρt)|E|
Theorem 1 のアルゴリズムによって
ρt|E| 少なくとも
(1 – 2√ ε/ρt- δ/2 )|E|(ρt-ρt+1) はカット
Theorem 5
Recursive-Spectral-Cut の近似率は 0.531128 － δ
証明

Download Report