半正定値計画を用いた 最大カット問題の .878 近似解法 ver. C.22 東京大学大学院工学系研究科 計数工学専攻 松井知己

Improved Approximation Algorithms for 文献紹介 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 V/U δ(U)：ｶｯﾄ w（U）：ｶｯﾄ重み14

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{ xtQx + cｔx | x ∈{0,1}n } (Q:対称行列） MAX CUT 問題の重要性 0-1変数2次計画問題(制約無し） max{ xtQx + cｔx | x ∈{0,1}n } (Q:対称行列） 人工頂点 n頂点のグラフ x i =1 δ( i ) i に接続する 枝集合

近似解法：近似精度の存在する解法． 発見的解法：近似精度は不明． 近似比率： （最大化問題の場合） α近似解法： 近似解法とは？ 近似解法：近似精度の存在する解法． 得られる解と最適解との距離の見積もりが存在． 発見的解法：近似精度は不明． 近似比率：　（最大化問題の場合） ＝（得られた解の目的関数値）／（最適値） α近似解法： 近似比率α以上の解を必ず求める解法．

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)(最適値)．

(1/2） [1976: Sahni and Gonzales] (1/2)+(1/2m) [1981: Vitany] 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次連続最適化問題に変形． ●半正定値計画緩和． ●ランダム化アルゴリズム．

max{∑w(i,j) ｄ(v(i )v( j)) | v(i )∈ S (∀ i ∈V )} 球面上の配置問題（図） グラフ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/π の球の表面． 球面上の配置問題 入力:無向グラフ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 }

max{∑w (i,j) ｄ(v(i )v( j)) | v(i )∈ S (∀ i ∈V )} 球面上の配置問題（再） グラフ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)} 定理 δ(U*)：最大カット． 球面上の配置問題(定理) max{∑w (i,j) ｄ(v(i )v( j)) | v(i )∈S　(∀i∈V)} 定理 δ(U*)：最大カット． v (i ∈ U* ), ∀ v∈S， v*(i )={ とおけば, - v (i∈ V－U* ), 　　　解 v*(i )は球面上の配置問題の最適解． 注：半円弧の長さ＝１ カット配置では， 目的関数値＝カットの重み． {i,j } v -v

∑w (i,j) ｄ(v*(i )v*( j))= w (U*)= (最大カットの値)． 定理の証明(上) 配置v* での目的関数値 ∑w (i,j) ｄ(v*(i )v*( j))= w (U*)= (最大カットの値)． (任意の配置vでの目的関数値)≦ w (U*) を示す． H：原点を境界に含む閉半空間． V(H)：v(i)のうちHに含まれる点集合． w（H)：V(H)に対応するカットの重み． 原点を境界に含む閉半空間 　全てを等確率で発生させる． 発生した閉半空間Hに対し， 　　　 w（H)の期待値は？ {i,j } H

原点を境界に含む閉半空間全てを等確率で発生． 発生した閉半空間Hに対し， w（H)の期待値は？ 定理の証明(中) 原点を境界に含む閉半空間全てを等確率で発生． 発生した閉半空間Hに対し， w（H)の期待値は？ 頂点i,j間の弧の長さ=ｄ(v(i )v( j))より， 発生した閉半空間が頂点i,jを分ける確率は， ｄ(v(i )v( j))/(大円の半円弧の長さ)=ｄ(v(i )v( j)) i ｄ(v(i )v( j)) j 半円弧の長さ=１

原点を境界に含む閉半空間全てを等確率で発生． 定理の証明(下) 原点を境界に含む閉半空間全てを等確率で発生． 発生した閉半空間Hに対し， w（H)の期待値は？ 　E[w（H)]=∑w　 (i,j) Pr[∂Hが頂点i,jを分ける] 　　　　　=∑w (i,j) ｄ(v(i )v( j)) w（H)は発生するカットの重みの期待値より， 　E[w（H)]≦ w (U*) 　(最大カット重み)． 以上より，任意の配置v(i )について， 　∑w　 (i,j) ｄ(v(i )v( j))= E[w（H)]≦ w (U*) ． {i,j } {i,j } {i,j }

max{∑w(i,j) ｄ(v(i )v( j)) | v(i )∈S (∀i∈V)} 定理 δ(U*)：最大カット． MAX CUT問題＝球面上の配置問題 max{∑w(i,j) ｄ(v(i )v( j)) | v(i )∈S　(∀i∈V)} 定理　　δ(U*)：最大カット． v (i ∈ U* ) ∀ v∈S， v*(i )={ - v (i∈ V-U* ) 　　　解 v*(i )は球面上の配置問題の最適解． MAX CUT問題と球面上の配置問題は 本質的に等価． {i,j }

max{∑w(i,j) ｄ(v(i )v( j)) | v(i )∈S (∀i∈V)} 球面上の配置からのｶｯﾄ生成 max{∑w(i,j) ｄ(v(i )v( j)) | v(i )∈S　(∀i∈V)} 任意の球面上の配置 v に対し，次が成り立つ． 原点を境界に含む閉半空間を 等確率で（多数）発生させると， (得られるカットの重みの期待値)=E[（H)] =∑{i,j }∈E w(i,j) Pr[∂Hが頂点i,jを分ける] =∑{i,j }∈E w(i,j) ｄ(v(i )v( j)) =(配置v に対応する目的関数値） 以上の重みのカットを 生成する事が出来る． {i,j } H

MAX CUT問題と頂点配置問題は本質的に等価． →頂点配置問題を緩和する． ∀v,∀v’∈ S , 頂点配置問題の緩和 MAX CUT問題と頂点配置問題は本質的に等価． 　　→頂点配置問題を緩和する． ∀v,∀v’∈ S , 　　ｆ(vv’)= v v’ 間の直線距離のπ/2倍の2乗． 　　（ｄ(vv’)=１ ⇔ v v’はSの直径 ⇔ ｆ(vv’)=１） →距離ｄをｆで置き換える． ｆ(vv’)=（π/2)2||v - v’||2 =(1/2)(1‐π2 vｔ v’） S 1/π d 1/2

max{∑w(i,j) ｄ(v(i )v( j)) | v(i )∈S (∀i∈V)} 緩和問題： 球面上の配置問題： max{∑w(i,j) ｄ(v(i )v( j)) | v(i )∈S　(∀i∈V)} 緩和問題： max{∑w(i,j) ｆ (v(i )v( j)) | v(i )∈S　(∀i∈V)} {i,j } {i,j }

⇒ ∑w(i,j) ｄ(v(i )v( j)) =∑w(i,j) ｆ (v(i )v( 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)) ∴最大カットの値 =最大カット配置をdで測った目的関数値 　　　　　=最大カット配置をf で測った目的関数値 ≦(緩和問題の最適値) ∵カット配置でなくて良い {i,j }

∀v,∀v’∈ S , ｄ(vv’)＞ 0.878 ｆ (vv’) ｄ(vv’)=θ/π ｆ (vv’)=（1-cosθ)/2 距離の比率 定理 ∀v,∀v’∈ S , ｄ(vv’)＞ 0.878 ｆ (vv’) ｄ(vv’)=θ/π ｆ (vv’)=（1-cosθ)/2 ｄ(vv’)／ｆ (vv’) 　≧ (2/π)(θ/（1-cosθ)） 1/π 1/2 d S θ min (2/π)(θ/（1-cosθ)）=0.878‥ 0≦θ≦π

０．８７８の比率を見るグラフ 0.878 ｆ ＝(1-cos(θ))/2 d=θ/π θ π π/2 1 0.8 0.6 0.4 0.2 d=θ/π θ π/2 π

∑w(i,j) ｄ(v’(i )v’( j)) 定理 v’(i ):緩和問題の最適解. v’(i ):緩和問題の最適解. 最適値の比率 定理　v’(i ):緩和問題の最適解. (配置v’(i )をdで測った目的関数値) 　 ≧0.878(最大カット重み) v’(i ):緩和問題の最適解. v*(i ):球面上の配置問題の最適解（最大カット配置）. ∑w(i,j) ｄ(v’(i )v’( j)) 　　　　≧0.878∑w(i,j) ｆ (v’(i )v’( j)) 　　　　≧0.878∑w(i,j) ｆ (v*(i )v*( j)) 　　　　=0.878∑w(i,j) ｄ(v*(i )v*( j) ) {i,j } {i,j } {i, j } {i, j }

定理 (緩和問題の最適解の目的関数値) 0.878近似解法 (2)球面配置v’(i )の目的関数値 以上のカットを生成する． ∑w(i,j) ｄ(v(i )v( j)) 以上のカットを生成出来る． 定理 (緩和問題の最適解の目的関数値) 　　　　　　≧0.878 (最大カットの重み) 0.878近似解法 (1)緩和問題の最適解配置v’(i )を求める． (2)球面配置v’(i )の目的関数値 　　　以上のカットを生成する． {i,j }

算定された近似比率 = 0.87856‥‥ いくつかのグラフでの (最大カット値)/(緩和問題の最適値) 近似比率の算定は緩くないか？ 算定された近似比率 = 0.87856‥‥ いくつかのグラフでの (最大カット値)/(緩和問題の最適値) 長さ5のサイクル: 0.88445‥‥ Petersen graph: 0.8787 [G&W 95］頂点103個のグラフ：0.8786

[Goemans and Williamson 95] ●球面上の配置問題の緩和問題を， 半正定値計画問題に変形する． 　　半正定値計画問題に変形する．

max{∑w (i,j) ｆ (v(i )v( j)) | v(i )∈S (∀i∈V)} 球面配置問題の緩和問題 球面上の配置問題=最大カット問題（MC）: max{∑w　 (i,j) ｄ(v(i )v( j)) | v(i )∈S　(∀i∈V)} 緩和問題（MC）： max{∑w　 (i,j) ｆ (v(i )v( j)) | v(i )∈S　(∀i∈V)} {i,j } {i,j }

max{∑w(i,j) ｆ (v(i )v( j)) | v(i )∈S (∀i∈V)} 半正定値行列の出現 MC max{∑w(i,j) ｆ (v(i )v( j)) | v(i )∈S (∀i∈V)} =　max{∑w(i,j) (1-π2v(i )ｔv( j) ) | v(i)∈S(∀i∈V)} 行列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)． が成り立つ． {i,j } {i,j }

max{∑w(i,j) (1-π2v(i )ｔv( j) ) | v(i)∈S(∀i∈V)} 半正定値計画への変形 MC max{∑w(i,j) (1-π2v(i )ｔv( j) ) | v(i)∈S(∀i∈V)} 行列Y=[ｙ　i　j]をｙ　i　j　=(πv(i))ｔ（πv(　j　)）と定義する． 　　　 変形　　　　　　　緩和 max.　∑w(i,j) (1-ｙ　i　j ) sub.to　 Y =[ｙ　i　j]は半正定値対称行列, 　　 ｙ　ii＝1　 (∀i∈V), 　　　　　Y= π2X　tX , 　X　=(v(1),..., v(n)).　× {i,j } {i,j }

max{∑w(i,j) (1-π2v(i )ｔv( j) ) | v(i)∈S(∀i∈V)} 半正定値計画との等価性 MC max{∑w(i,j) (1-π2v(i )ｔv( j) ) | v(i)∈S(∀i∈V)} 　|| （S はn 次元球面の時,２つの問題は等価） max.　∑w(i,j) (1-ｙ　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の許容解. 緩和問題の最適解と一致する許容解が作れる． {i,j } {i,j }

sub. to Y =[ｙ i j]は半正定値対称行列, ｙ ii＝1 (∀i∈V)． 半正定値計画の一般形 max.　∑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 . 半正定値計画問題は内点法で効率良く解ける． {i,j }

凸領域で，線形目的関数を最大化する問題． ⇒山登り法で最大解に到達できる． ≡{Y∈Rn×n|Y は半正定値}は凸錐 半正定値計画は 何故 効率的に解けるか(1) max.　 W･Y sub. to　 Y は半正定値対称行列, 　　 Qi･Y=bi　 ( i∈{1,2,...,m})． ただし，W, Qi　は対称行列, A･B=∑i∑j ai j bi j . 凸領域で，線形目的関数を最大化する問題． ⇒山登り法で最大解に到達できる． ≡{Y∈Rn×n|Y は半正定値}は凸錐 ：半正定値錐

を でおきかえれば線形計画(LP)⇒LPの解法を拡張 半正定値計画は 何故 効率的に解けるか（２） max.　 W･Y sub. to　 Y∈ , 　　 Qi･Y=bi　 ( i∈{1,2,...,m})． ただし，W, Qi　は対称行列, A･B=∑i∑j ai j bi j . ≡{Y∈Rn×n|Y は半正定値}は凸錐 は自己双対錐である. (非負象限 と似ている) を でおきかえれば線形計画(LP)⇒LPの解法を拡張

問題SDP(μ) max. W･Y＋μlog det Y sub.to Y は半正定値対称行列, 半正定値計画問題を解く内点法 問題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 0.96988 36.28 100 20 0.96783 323.08 Sun SPARC station 1 200 5 0.97209 4629.62 B 50 50 0.97202 23.06 Code:Vanderbei 100 20 0.97097 217.42 [1995] 200 5 0.97237 2989.00 C 50 50 0.95746 23.53 カットは50個生成 100 20 0.94214 306.84 200 5 0.92362 2546.42 D 50 50 0.95855 27.35 100 20 0.93984 355.32 200 5 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 ] 問題 1996年 1999年 比率 . g(n ,枝密度[%]) ( [秒],[Mbyte]) ([秒],[Mbyte]) g124.02 ( 636.5, 5.1) ( 9.1, 5.0) 0.9648 g124.04 ( 610.3, 5.1) ( 9.4, 5.0) 0.9374 g124.08 ( 637.1, 5.1) ( 9.4, 5.0) 0.9470 g124.16 ( 607.0, 5.1) ( 9.4, 5.0) 0.9625 g250.01 ( 7948.5, 23.5) ( 82.7, 20.0) 0.9518 g250.02 ( 7407.6, 23.5) ( 79.8, 20.0) 0.9516 g250.04 ( 7290.7, 23.5) ( 80.3, 20.0) 0.9244 g250.08 ( 7505.7, 23.5) ( 80.2, 20.0) 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問題（Satisfiability problem：充足可能性問題) ブール変数：U=｛a1，a2，a3 } クローズ：Γ=｛C1 ，C２，C３， C４， C５， C６ ｝ C1 = ｛ a2 }， C２ = ｛ ￢a1， a2，￢a3 } ， C３ = ｛ ￢a1，￢a2，￢a3 } ， C４ = ｛ ￢a1，￢a2， a3 } ， C５ = ｛ a1，￢a2 } ， C６ = ｛ a1， a3 } （￢a　は　a　の否定を意味する．） Γ中のクローズを 　　　全て真とする． U への真偽割当は 　　　あるか？ クローズが真 　⇔クローズ中のリテラルが 　　　少なくとも１つ真

Γ中のクローズを全て真とする, U への真偽割当は存在しない． SAT問題(問題例と真偽割当) 　U=｛ a1， a2， a3 } T T F C1 = ｛ a2 } ⇒　T C２ = ｛ ￢a1， a2，￢a3 } ⇒　T C３ = ｛ ￢a1，￢a2，￢a3 } ⇒　T C４ = ｛ ￢a1，￢a2， a3 } ⇒　F C５ = ｛ a1，￢a2 } ⇒　T C６ = ｛ a1， a3 } ⇒　T Γ中のクローズを全て真とする,　U への真偽割当は存在しない．

SAT問題（Satisfiability problem：充足可能性問題) 入力:ブール変数U，クローズの集合Γ． 　 Γ中のクローズを全て真となる． リテラル：入力されたブール変数，またはその否定 クローズ：リテラルの集合 クローズが真⇔クローズ中のリテラルの１つ以上が真 k SAT:(ｸﾛｰｽﾞ中のﾘﾃﾗﾙ数)≦ｋ SAT：NP‐完全性が示された最初の問題[Cook71]. 3SAT：NP-完全. 2SAT:多項式時間算法がある.

T T F 重み C1 = ｛ a2 } ４⇒ T 4 C２ = ｛ ￢a1， a2，￢a3 } １⇒ T 1 MAX SAT(問題例) U=｛ a1， a2， a3 } 　　　例題提供:宮本裕一郎 　　　　　　T 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 真となるクローズ重みの総和を最大化． クローズが真 ∥ クローズ中の リテラルが 少なくとも１つ真 総和=２７ クローズ重み和　２３

MAX SAT問題 入力:ブール変数U，クローズの集合Γ． 非負整数のクローズ重みw:Γ→Z． 問題：Γ中の真となるクローズ重みの和が MAX ２SAT問題もNP‐困難 　　　　　[ Garey，Johnson and Stockmeyer 71]

制約付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’) 半正定値計画： max ∑w(i,j) (1-ｙ　i　j ) Y =[ｙ　i　j] は半正定値対称行列, 　　 ｙ　ii＝1 (∀i∈V), ｙ　ij =1 (∀｛i,j｝∈E’) {i,j } {i,j }

制約付MAX CUT問題：辺集合E’を含む 最大重みｶｯﾄを求める E’の枝 E’の枝の両端点は 直径の両端に配置する． 　　　　　　　　　　　　　最大重みｶｯﾄを求める 　　　　E’の枝 　　　　　　　　　　　　　　E’の枝の両端点は 　　　　　　　　　　　　　直径の両端に配置する． ｅ ｄ ａ ｂ ａ ｃ ｄ ｅ ｃ ｂ

MAX 2SAT問題⇒制約付MAX CUT問題 （LAST) C1 = ｛ a2 } 　４ C２ = ｛ ￢a1， a3 } １ C３ = ｛ a1，￢a2， } ６ E’の（重み=0） a1 a2 a3 ４ １/2 ６/2 E’の枝を含むｶｯﾄの重み 　　　　　|| a0と同じ側に入らないリテラルを真とした，クローズの重みの総和 a0 ６/2 １/2 １/2 ６/2 ￢a1 ￢a2 ￢a3

まとめ

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.875⇒P=NP) 0.75=1- (1/2)2, 0.875=1- (1/2)3.

おしまい