近似解法 Þ - @niftyホームページサービス

半正定値計画を用いた
最大カット問題の .878 近似解法
ver. C.22
東京大学大学院工学系研究科
計数工学専攻
松井知己
文献紹介
Improved Approximation Algorithms for
Maximum Cut and Satisfiability Problems
Using Semidefinite Programming,
M. X. Goemans and D. P. Williamson,
J. ACM, 42 (1995), pp.1115-1145.
Approximation Algorithm
：近似解法
Maximum Cut Problem
：最大カット問題
Maximum Satisfiability Problem：最大充足可能性問
題？
Semidefinite Programming
：半正定値計画
MAX CUT問題(問題例)
カット重み=８
２
３
４
５
４
５
３
カット重み=１４
３
２
４
４
５
５
１
３
１
ｶｯﾄの定義
グラフG=（V,E) V：頂点集合 E：枝集合
４
５
３
５
２
３
４
U⊆V
δ(U)：ｶｯﾄ
w（U）：ｶｯﾄ重み14
V/U
１
MAX CUT問題(定義)
MAX CUT問題
入力:無向グラフG=(V,E)，非負整数枝重みw:E→Z+．
問題：G中のカットで，
重み最大となるものを求めよ．
頂点部分集合U⊆V に対するカット：
δ(U)=｛e∈E |e はU中の頂点とU に無い頂点を結
ぶ｝
カットδ(U)の重さ：
w(U)= δ(U)中の枝重みの総和．
MAX CUT問題：max { w(U ) | U⊆V }
NP‐困難[ Karp 72]
MAX CUT 問題の重要性
0-1変数2次計画問題(制約無し）
n
t
ｔ
max{ x Qx + c x | x ∈{0,1} } (Q:対称行列）
人工頂点
n頂点のグラフ
x i =1
ci +

j (i)
qij
δ( i )
i に接続する枝集合
ci q ij c j
–qij
近似解法とは？
近似解法：近似精度の存在する解法．
得られる解と最適解との距離の見積もりが存在．
発見的解法：近似精度は不明．
近似比率：（最大化問題の場合）
＝（得られた解の目的関数値）／（最適値）
α近似解法：
近似比率α以上の解を必ず求める解法．
MAX CUTの1/2 近似解法
●非常に単純なランダム化算法．
１/２近似解法
MAX CUT問題：max { w(U) | U ⊆V }
１/２近似解法：
各頂点を１/２の確率でUに入れる．
解析：各枝について，両端の内
ちょうど一方がUに入る確率は1/2．
カットの重みの期待値ｚは，
ｚ＝∑e ∈E w（e ） Pr[枝e がカットに入る]
＝∑e ∈E w（e ）(1/2)
＝(1/2) (枝重みの総和)
≧ (1/2)(最大カット重み) =(1/2)(最適値)．
MAX CUTの近似解法の歴史
(1/2）
[1976: Sahni and Gonzales]
(1/2)+(1/2m)
[1981: Vitany]
(1/2)+((n -1)/4m)[1982: Poljak and Turzik]
(1/2)+(1/2n)
[1991: Haglin and Venkatesan]
(1/2)+(1/2D)
[1995: Hofmeister and Lefmann]
n :頂点数
m :枝数
D :最大次数（次数：頂点につながる枝数）
0.878
[1995: Goemans and Williamson]
MAX CUTの0.878 近似解法
[Goemans and Williamson 95]
●MAX CUTを
非凸2次連続最適化問題に変形．
●半正定値計画緩和．
●ランダム化アルゴリズム．
球面上の配置問題（図）
グラフGの頂点を球面S上に配置して，
枝重みと距離の積の総和を最大化する．
max{∑w(i,j) ｄ(v(i )v( j)) | v(i )∈ S (∀ i ∈V )}
{i,j }
球面上の配置問題
入力:無向グラフG=(V,E)，非負枝重みw:E→ Z+，
S：原点を中心とし，半径1/π の球の表面．
次元は任意． (大円の半円弧の長さ=１)．
∀v,∀v’∈ S ,
ｄ(vv’)= v と v’を結ぶ大円弧の短い方の長さ．
球面上の配置問題
グラフGの頂点をS上に配置して，
枝重みと距離の積の総和を最大化する．
max{∑w(i,j) ｄ(v(i )v( j)) | v(i )∈ S (∀ i ∈V )}
{i,j }
球面上の配置問題（再）
グラフGの頂点を球面S上に配置して，
枝重みと距離の積の総和を最大化する．
max{∑w(i,j) ｄ(v(i )v( j)) | v(i )∈ S (∀ i ∈V )}
{i,j }
球面上の配置問題(定理)
max{∑w(i,j) ｄ(v(i )v( j)) | v(i )∈S (∀i∈V)}
{i,j }
定理
δ(U*)：最大カット．
v (i ∈ U* ),
∀ v∈S， v*(i )=
とおけば,
- v (i∈ V－U* ),
解 v*(i )は球面上の配置問題の最適解．
{
注：半円弧の長さ＝１
カット配置では，
目的関数値＝カットの重み．
-v
v
定理の証明(上)
配置v* での目的関数値
∑w(i,j) ｄ(v*(i )v*( j))= w (U*)= (最大カットの値)．
{i,j }
(任意の配置vでの目的関数値)≦ w (U*) を示す．
H：原点を境界に含む閉半空間．
V(H)：v(i)のうちHに含まれる点集合．
w（H)：V(H)に対応するカットの重み．
原点を境界に含む閉半空間
全てを等確率で発生させる．
発生した閉半空間Hに対し，
w（H)の期待値は？
定理の証明(中)
原点を境界に含む閉半空間全てを等確率で発生．
発生した閉半空間Hに対し， w（H)の期待値は？
頂点i,j間の弧の長さ=ｄ(v(i )v( j))より，
発生した閉半空間が頂点i,jを分ける確率は，
ｄ(v(i )v( j))/(大円の半円弧の長さ)=ｄ(v(i )v( j))
i
j
半円弧の長さ=１
ｄ(v(i )v( j))
定理の証明(下)
原点を境界に含む閉半空間全てを等確率で発生．
発生した閉半空間Hに対し， w（H)の期待値は？
E[w（H)]=∑w (i,j) Pr[∂Hが頂点i,jを分ける]
{i,j }
=∑w (i,j) ｄ(v(i )v( j))
{i,j }
w（H)は発生するカットの重みの期待値より，
E[w（H)]≦ w (U*) (最大カット重み)．
以上より，任意の配置v(i )について，
∑w (i,j) ｄ(v(i )v( j))= E[w（H)]≦ w (U*) ．
{i,j }
MAX CUT問題＝球面上の配置問題
max{∑w(i,j) ｄ(v(i )v( j)) | v(i )∈S (∀i∈V)}
{i,j }
定理
δ(U*)：最大カット．
v (i ∈ U* )
∀ v∈S， v*(i )=
- v (i∈ V-U* )
解 v*(i )は球面上の配置問題の最適解．
{
MAX CUT問題と球面上の配置問題は
本質的に等価．
球面上の配置からのｶｯﾄ生成
max{∑w(i,j) ｄ(v(i )v( j)) | v(i )∈S (∀i∈V)}
{i,j }
任意の球面上の配置 v に対し，次が成り立つ．
原点を境界に含む閉半空間を
等確率で（多数）発生させると，
(得られるカットの重みの期待値)=E[（H)]
= {i,j }∈E w(i,j) Pr[∂Hが頂点i,jを分ける]
∑
=∑ i,j
{ }∈E
w(i,j) ｄ(v(i )v( j))
=(配置v に対応する目的関数値）
以上の重みのカットを
生成する事が出来る．
頂点配置問題の緩和
MAX CUT問題と頂点配置問題は本質的に等価．
→頂点配置問題を緩和する．
∀v,∀v’∈ S ,
ｆ(vv’)= v v’ 間の直線距離のπ/2倍の2乗．
（ｄ(vv’)=１ ⇔ v v’はSの直径 ⇔ ｆ(vv’)=１）
→距離ｄをｆで置き換える．
S
ｆ(vv’)=（π/2)2||v - v’||2
1/π
=(1/2)(1‐π2 vｔ v’）
1/2
f
d
緩和問題
球面上の配置問題：
max{∑w(i,j) ｄ(v(i )v( j)) | v(i )∈S (∀i∈V)}
{i,j }
緩和問題：
max{∑w(i,j) ｆ (v(i )v( j)) | v(i )∈S (∀i∈V)}
{i,j }
なぜ緩和問題になっているのか？
カット配置 v’ :
∃ U ：頂点部分集合．
v (i ∈ U )
∃ v∈S， v’(i )=
- v (i∈ V-U).
{
v’ がカット配置⇔∀i,∀j, ｄ(v(i )v( j))∈{0,1}
⇔ ∀i,∀j, f (v(i )v( j)) ∈{0,1}
⇒ ∑w(i,j) ｄ(v(i )v( j)) =∑w(i,j) ｆ (v(i )v( j))
{i,j }
{i,j }
∴最大カットの値
=最大カット配置をdで測った目的関数値
=最大カット配置をf で測った目的関数値
≦(緩和問題の最適値) ∵カット配置でなくて良い
距離の比率
定理
∀v,∀v’∈ S , ｄ(vv’)＞ 0.878 ｆ (vv’)
ｄ(vv’)=θ/π
ｆ (vv’)=（1-cosθ)/2
ｄ(vv’)／ｆ (vv’)
≧ (2/π)(θ/（1-cosθ)）
min (2/π)(θ/（1-cosθ)）=0.878‥
0≦θ≦π
f
S
1/π
1/2
θ
d
０．８７８の比率を見るグラフ
1
0.878
0.8
0.6
0.4
ｆ＝(1-cos(θ))/2
0.2
0
0.878(1-cos(θ))/2
d=θ/π
π/2
π
θ
最適値の比率
定理 v’(i ):緩和問題の最適解.
(配置v’(i )をdで測った目的関数値)
≧0.878(最大カット重み)
v’(i ):緩和問題の最適解.
v*(i ):球面上の配置問題の最適解（最大カット配置）.
{i,j }
∑w(i,j) ｄ(v’(i )v’( j))
≧0.878∑w(i,j) ｆ (v’(i )v’( j))
{i,j }
≧0.878∑w(i,j) ｆ (v*(i )v*( j))
{i, j }
{i, j }
0.878近似解法
任意の球面配置vに対し，原点を境界に含む閉半空間
全てを等確率で発生させる事により, vの目的関数値
w(i,j) ｄ(v(i )v( j)) 以上のカットを生成出来る．
∑
{i,j }
定理 (緩和問題の最適解の目的関数値)
≧0.878 (最大カットの重み)
0.878近似解法
(1)緩和問題の最適解配置v’(i )を求める．
(2)球面配置v’(i )の目的関数値
以上のカットを生成する．
近似比率の算定は緩くないか？
算定された近似比率 = 0.87856‥‥
いくつかのグラフでの
(最大カット値)/(緩和問題の最適値)
長さ5のサイクル: 0.88445‥‥
Petersen graph: 0.8787
[G&W 95］頂点103個のグラフ：0.8786
半正定値計画
[Goemans and Williamson 95]
●球面上の配置問題の緩和問題を，
半正定値計画問題に変形する．
球面配置問題の緩和問題
球面上の配置問題=最大カット問題（MC）:
max{∑w (i,j) ｄ(v(i )v( j)) | v(i )∈S (∀i∈V)}
{i,j }
緩和問題（MC）：
max{∑w (i,j) ｆ (v(i )v( j)) | v(i )∈S (∀i∈V)}
{i,j }
半正定値行列の出現
MC
max{∑w(i,j) ｆ (v(i )v( j)) | v(i )∈S (∀i∈V)}
{i,j }
2
ｔv( j) ) | v(i)∈S(∀i∈V)}
= max{{i,j
(1-π
v(i
)
∑w(i,j)
}
行列Y=[ｙ i j]をｙ i j =(πv(i))ｔ（πv( j )）と定義する.
X =(v(1),..., v(n))とすると， Y= π2X tX より,
(1) Y は半正定値対称行列,
(2) ｙ i i＝1 (∀i∈V)．
が成り立つ．
半正定値計画への変形
MC
max{∑w(i,j) (1-π2v(i )ｔv( j) ) | v(i)∈S(∀i∈V)}
{i,j }
行列Y=[ｙ i j]をｙ i j =(πv(i))ｔ（πv( j )）と定義する．
変形
緩和
max. ∑w(i,j) (1-ｙ i j )
{i,j }
sub.to Y =[ｙ i j]は半正定値対称行列,
ｙ ii＝1 (∀i∈V),
Y= π2X tX , X =(v(1),..., v(n)). ×
半正定値計画との等価性
MC
max{∑w(i,j) (1-π2v(i )ｔv( j) ) | v(i)∈S(∀i∈V)}
{i,j }
|| （S はn 次元球面の時,２つの問題は等価）
max. ∑w(i,j) (1-ｙ i j )
{i,j }
sub.to Y =[ｙ i j]は半正定値対称行列,
ｙ ii＝1 (∀i∈V)．
∵（1/π2）Y をCholesky分解→（1/π2）Y = X tX.
X =(v(1),..., v(n))とおけば， v(i) はMCの許容解.
緩和問題の最適解と一致する許容解が作れる．
半正定値計画の一般形
max. {i,j
∑w(i,j)
(1-ｙ i j )
}
sub. to Y =[ｙ i j]は半正定値対称行列,
ｙ ii＝1 (∀i∈V)．
一般の半正定値計画問題
max. W･Y
sub. to Y は半正定値対称行列,
Qi･Y=bi ( i∈{1,2,...,m})．
ただし，W, Qi は対称行列, A･B=∑i∑j aij bij .
半正定値計画問題は内点法で効率良く解ける．
半正定値計画は何故効率的に解けるか(1)
max.
W･Y
sub. to Y は半正定値対称行列,
Qi･Y=bi ( i∈{1,2,...,m})．
ただし，W, Qi は対称行列, A･B=∑i∑j ai j bi j .
凸領域で，線形目的関数を最大化する問題．
⇒山登り法で最大解に到達できる．
S ≡{Y∈Rn×n|Y は半正定値}は凸錐
n
+
S
n
：半正定値錐
+
半正定値計画は何故効率的に解けるか（２）
max.
W･Y
sub. to Y∈ S +n,
Qi･Y=bi ( i∈{1,2,...,m})．
ただし，W, Qi は対称行列, A･B=∑i∑j ai j bi j .
n
+
S ≡{Y∈Rn×n|Y は半正定値}は凸錐
n
S + は自己双対錐である.
Y S  ZS , YZ  0
n
+
k
+
(非負象限 R
n
+
{yR | y0}と似ている)
k
y R  zR , y z  0
k
k
t
+
+
S +n を R+nn でおきかえれば線形計画(LP)⇒LPの解法を拡張
半正定値計画問題を解く内点法
問題SDP
max. W･Y
sub.to Y は半正定値対称行列,
Qi･Y=bi ( i∈{1,2,...,m})．
問題SDP(μ) max. W･Y＋μlog det Y
sub.to Y は半正定値対称行列,
Qi･Y=bi ( i∈{1,2,...,m})．
Y (μ)：問題SDP(μ) の最適解
中心パス {Y (μ) |μ> 0 }をNewton法で追跡する．
多項式時間解法が存在．
最適解
計算機実験
ｸﾞﾗﾌ頂点数問題数
A
50
50
100
20
200
5
B
50
50
100
20
200
5
C
50
50
100
20
200
5
D
50
50
100
20
200
5
比率時間[秒］
0.96988
36.28
0.96783
323.08 Sun SPARC station 1
0.97209 4629.62
0.97202
23.06 Code:Vanderbei
0.97097
217.42
[1995]
0.97237 2989.00
0.95746
23.53 カットは50個生成
0.94214
306.84
0.92362 2546.42
0.95855
27.35
0.93984
355.32
0.93635 10709.42 （３時間程度）
計算機実験 [藤沢克樹 1996: RAMP シンポジウム予稿集]
問題
比率
g(n ,枝密度[%]) SDP[秒]
RANDOM SDP-R
LOCAL
TABU .
g124.02
636.5
0.6761 0.9648 0.9507 0.9648
g124.04
610.3
0.7040 0.9374 0.9411 0.9485
g124.08
637.1
0.7781 0.9470 0.9513 0.9534
g124.16
607.0
0.8052 0.9625 0.9648 0.9648 .
g250.01
7948.5
0.6303 0.9518 0.9140 0.9612
g250.02
7407.6
0.6612 0.9516 0.9118 0.9438
g250.04
7290.7
0.7318 0.9244 0.9376 0.9448
g250.08
7505.7
0.7712 0.9454 0.9513 0.9567
(2時間程度)
RANDOM,LOCAL,TABUは100秒間繰り返したもの．
SDP-Rは，SDPを解いたのち，100秒間ランダムにカットを生成．
1996年：SDPA Ver.1.0 ：Sun SPARC Station 20 125MHz
SDP計算機実験 [藤沢克樹 (京大建築）1996,1999 ]
問題
g(n ,枝密度[%])
g124.02
g124.04
g124.08
g124.16
g250.01
g250.02
g250.04
g250.08
(
(
(
(
(
(
(
(
(
1996年
[秒],[Mbyte])
636.5, 5.1)
610.3, 5.1)
637.1, 5.1)
607.0, 5.1)
7948.5, 23.5)
7407.6, 23.5)
7290.7, 23.5)
7505.7, 23.5)
1999年
([秒],[Mbyte])
( 9.1, 5.0)
( 9.4, 5.0)
( 9.4, 5.0)
( 9.4, 5.0)
( 82.7, 20.0)
( 79.8, 20.0)
( 80.3, 20.0)
( 80.2, 20.0)
比率
.
0.9648
0.9374
0.9470
0.9625
0.9518
0.9516
0.9244
0.9454
1996年：SDPA Ver.1.0 ：Sun SPARC Station 20 125MHz
1999年：SDPA Ver.4.30：DEC ALPHA 21164
600MHz
MAX 2SATの0.878 近似解法
[Goemans and Williamson 95]
●MAX ２SATを
制約付MAX CUT問題に変形する．
（スライド１０枚）
へ）
（まとめ
SAT問題(問題例)
SAT問題（Satisfiability problem：充足可能性問題)
ブール変数：U=｛a1，a2，a3 }
クローズ：Γ=｛C1 ，C２，C３， C４， C５， C６｝
C1 = ｛
a2
}，
Γ中のクローズを
C２ = ｛￢a1， a2，￢a3 } ，
全て真とする．
C３ = ｛￢a1，￢a2，￢a3 } ， U への真偽割当は
あるか？
C４ = ｛￢a1，￢a2， a3 } ，
C５ = ｛ a1，￢a2
} ，クローズが真
⇔クローズ中のリテラルが
C６ = ｛ a1，
a3 }
少なくとも１つ真
（￢a は a の否定を意味する．）
SAT問題(問題例と真偽割当)
U=｛ a1， a2， a3 }
T
T
F
C1 = ｛
a2
}⇒
C２ = ｛￢a1， a2，￢a3 } ⇒
C３ = ｛￢a1，￢a2，￢a3 } ⇒
C４ = ｛￢a1，￢a2， a3 } ⇒
C５ = ｛ a1，￢a2
}⇒
C６ = ｛ a1，
a3 } ⇒
T
T
T
F
T
T
Γ中のクローズを全て真とする,
U への真偽割当は存在しない．
SAT問題（定義）
SAT問題（Satisfiability problem：充足可能性問題)
入力:ブール変数U，クローズの集合Γ．
質問：∃? U への真偽割当，
Γ中のクローズを全て真となる．
リテラル：入力されたブール変数，またはその否定
クローズ：リテラルの集合
クローズが真⇔クローズ中のリテラルの１つ以上が真
k SAT:(ｸﾛｰｽﾞ中のﾘﾃﾗﾙ数)≦ｋ
SAT：NP‐完全性が示された最初の問題[Cook71].
3SAT：NP-完全. 2SAT:多項式時間算法がある.
MAX SAT(問題例)
a2， a3 }
例題提供:宮本裕一郎
T
F 重み
クローズが真
C1 = ｛
a2
} ４⇒ T 4
∥
クローズ中の
C２ = ｛￢a1， a2，￢a3 } １⇒ T 1
リテラルが
C３ = ｛￢a1，￢a2，￢a3 } ６⇒ T 6
少なくとも１つ真
C４ = ｛￢a1，￢a2， a3 } ４⇒ F×
C５ = ｛ a1，￢a2
} ３⇒ T 3 総和=２７
C６ = ｛ a1，
a3 } ９⇒ T 9 クローズ重み和２３
U=｛
a1，
T
真となるクローズ重みの総和を最大化．
MAX SAT問題（定義）
MAX SAT問題
入力:ブール変数U，クローズの集合Γ．
非負整数のクローズ重みw:Γ→Z．
問題：Γ中の真となるクローズ重みの和が
最大となる，Uへの真偽割当を求めよ．
各クローズ中のリテラルがｋ個以下⇒ MAX ｋ SAT
MAX ２SAT問題もNP‐困難
[ Garey，Johnson and Stockmeyer 71]
制約付MAX CUT問題（定義）
制約付MAX CUT問題 ← MAX 2SAT
入力:無向グラフG=(V,E ), 枝集合E ’⊆E ,
非負枝重みw:E→Z+．
問題：G 中のカットで,枝集合E ’を含み,
重み最大となるものを求めよ．
球面上の配置問題：
v(i )∈S (∀i∈V) ，
max ∑w(i,j) ｄ(v(i )v( j)) ｄ(v(i )v( j))=1 (∀｛i,j｝∈E’)
{i,j }
半正定値計画：
max ∑w(i,j) (1-ｙ i j ) Y =[ｙ i j] は半正定値対称行列,
{i,j }
ｙ ii＝1 (∀i∈V), ｙ ij =1 (∀｛i,j｝∈E’)
制約付MAX CUT問題（問題例）
制約付MAX CUT問題：辺集合E’を含む
最大重みｶｯﾄを求める
E’の枝
E’の枝の両端点は
ｅ
直径の両端に配置する．
ｄ
ａ
ｅ
ｃ
ａ
ｄ
ｂ
ｂ
ｃ
MAX 2SAT問題⇒制約付MAX CUT問題（LAST)
MAX 2SAT問題は，
制約付MAX CUT問題に変形できる．
C1 = ｛
a2
} ４
C２ = ｛￢a1，
a3 } １
C３ = ｛ a1，￢a2，
} ６
a1
４
６/2
６/2
a0
１/2
￢a1
６/2
a2
a3
１/2
１/2
￢a2
￢a3
E’の（重み
=0）
E’の枝を含むｶｯﾄの重み
||
a0と同じ側に入らない
リテラルを真とした，
クローズの重みの総和
まとめ
Goemans and Williamson の結果
問題
近似比：(既存）→(G&W)
MAX CUT （非負枝重み）：0.5 → 0.878
MAX 2SAT
：0.75→ 0.878
MAX SAT
：0.75→ 0.7584
MAX DICUT
：0.25→ 0.79607
半正定値緩和＋ランダム化算法
MAX k SAT の多項式時間近似解法の現在
MAX SAT 0.75
[Goemans and Williamson 94]
線形計画緩和を用いたもの．
MAX SAT 0.7584 [Goemans and Williamson 95]
線形計画緩和＋半正定値緩和.
MAX SAT 0.770 [Asano 97]
MAX CUT問題に近似比率 83/84 より良い
多項式時間近似算法が存在するならば、P=NP.
MAX 2SAT 0.878 [Goemans and Williamson 95]
制約付きMAX CUTに変形＋半正定値緩和
MAX 2SAT 0.931 [Feige and Goemans 95] (95/96⇒P=NP)
MAX 3SAT 0.875 ？ [Karloff and Zwick 97]
0.75=1- (1/2)2,
0.875=1- (1/2)3.
(0.875⇒P=NP)
おしまい

Download Report