東京大学大学院工学系研究科 計数工学専攻 松井知己 組合せ最適化問題の近似解法 東京大学大学院工学系研究科 計数工学専攻 松井知己

近似解法とは？ MAX SAT問題の近似解法 １/２近似解法 0．632近似解法 ３/４近似解法 MAX CUT問題 0．878近似解法 発表の目次 近似解法とは？ MAX SAT問題の近似解法 １/２近似解法　 0．632近似解法 ３/４近似解法 MAX CUT問題 0．878近似解法 半正定値計画 MAX ２SAT問題の0．878近似解法

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

MAX SATの近似解法

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，クローズの集合Γ． 質問：∃? U への真偽割当， 　 Γ中のクローズを全て真となる． リテラル：入力されたブール変数，またはその否定 クローズ：リテラルの集合 クローズが真⇔クローズ中のリテラルが 　　　　　　　　　　少なくとも１つは真 NP‐完全である事が示された最初の問題． 　　　　　　　　　　　　　　[Cook71]

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，クローズの集合Γ． 非負整数のクローズ重みｗ:Γ→Z． 問題：Γ中の真となるクローズ重みの和が MAX ２SAT問題もNP‐困難 　　　　　[ Garey，Johnson and Stockmeyer 71]

[D.S.Johnson 74] ●非常に単純なランダム化算法． MAX SATの1/2 近似解法 [D.S.Johnson 74] ●非常に単純なランダム化算法．

１/２近似解法： 各ブール変数を１/２の確率で真とする． 1/2 1/2 1/2 （重み総和=27） １/２近似解法(数値例) １/２近似解法： 各ブール変数を１/２の確率で真とする． 　　　　　 1/2 1/2 1/2　 （重み総和=27） C1 = ｛ a2 } 　４×(1/2) =2 C２ = ｛ ￢a1， a2，￢a3 } 　１×(7/8) =7/8 C３ = ｛ ￢a1，￢a2，￢a3 } ６×(7/8) =21/4 C４ = ｛ ￢a1，￢a2， a3 } 　４×(7/8) =7/2 C５ = ｛ a1，￢a2 } 　３×(3/4) =9/4 C６ = ｛ a1， a3 } ９×(3/4) =27/4 真となるクローズ重みの総和の期待値=22　

１/２近似解法： 各ブール変数を１/２の確率で真とする． 解析：リテラルをｋ個含むクローズが 真となる確率は 1-(1/2)kとなる． 真となるクローズの重みの期待値ｚは， ｚ　＝∑{　Pr[C　が真]w（C ）｜C　∈Γ　} 　＝∑{ ( 1-(1/2)k )w （C ）｜C∈Γ，|C |=ｋ　} 　≧∑{ (1/2)w（C ）｜C∈Γ　} (重みの総和)≧(最適値)より， ｚ≧∑{ (1/2)w（C ）|C∈Γ　} ≧ (1/2)*最適値．

リテラルをｋ個以上含むクローズが 真となる確率は 1-(1/2)k以上となる． 任意のクローズが リテラルをｋ個以上含むならば， 　リテラルをｋ個以上含むならば， 　1/2　近似解法ではなく， 　 1-(1/2)k　近似解法となる．

[Goemans and Williamson 94] ●線形緩和問題を用いる． ●問題例によって確率を変える ランダム化算法． MAX SATの0.632 近似解法 [Goemans　and Williamson 94] ●線形緩和問題を用いる． ●問題例によって確率を変える 　　ランダム化算法．

s.t. xi+xn+i =1 (∀ｉ ), xi∈｛0,1｝ (∀ｉ )， 整数計画への定式化 ブール変数の集合Ｕ =｛a1,a2,...,an｝， クローズの集合Γ= ｛C1,C2,...,Cｍ｝ リテラルの添え字集合｛1,2,...,n,n+1,...,2n｝ ただし１≦i≦nならば，iはリテラルai に， n＋１≦n＋i≦２nならば，n＋i はリテラル￢ai に対応． 変数x1,x2,...,xn , xn+1,xn+2,...,x2n,z 1,z 2,...,z ｍ xi =1　⇔　リテラルai が真， z ｊ =1　⇔　クローズCｊ が真． MS: ｊ＝１ ｍ max.∑w j z j s.t. xi+xn+i　=1 (∀ｉ　), xi∈｛0,1｝ (∀ｉ　)， 　 z j ≦∑ xi (∀ｊ),　z j ∈｛0,1｝ (∀ｊ　)． 　　　　　　　　　　　　　 i ∈ cｊ

s.t. xi+xn+i =1 (∀ｉ ), 0≦xi≦1 (∀ｉ )， z j ≦∑ xi (∀ｊ), 0≦z j ≦1 (∀ｊ )． 線形緩和問題 ランダム化算法： （x*，ｚ*）線形緩和問題の最適解． 各ブール変数 ai を確率 xi*で真とする． max.∑w j z j s.t. xi+xn+i　=1 (∀ｉ　), 0≦xi≦1 (∀ｉ　)， 　 z j ≦∑ xi (∀ｊ), 0≦z j ≦1 (∀ｊ　)． 　　　　　　　　　　　　　 ｊ＝１ ｍ i ∈ cｊ MS:

x4 + x2 + x6≧ z2 x4 + x5 + x6≧ z3 x4 + x5 + x3≧ z4 x1 + x5 ≧ z5 ランダム化算法(数値例) max.4z1+1z2+6z3+4z4+3z5+9z6 s.t. x2 ≧ z1 　　　　x4 + x2 + x6≧ z2 x4 + x5 + x6≧ z3 x4 + x5 + x3≧ z4 x1 + x5 ≧ z5 x1 + x3≧ z6 xi + xn+i = 1, 0≦xi , xn+i ≦1(∀ i ) ｛ a2 } 　４ ｛ ￢a1， a2，￢a3 } 　１ ｛ ￢a1，￢a2，￢a3 } ６ ｛ ￢a1，￢a2， a3 } 　４ ｛ a1，￢a2 } 　３ ｛ a1， a3 } ９ 期待値＝21.4 ≧ 0.632*ＭＳの最適値≧ 0.632ＭＳの最適値 9*(1ー(1/4)(1/2)) ランダム化算法： 　線形緩和問題の最適解 x* =(3/4,3/4,1/2,1/４,1/４,1/2) 　 ＭＳの最適値＝26．⇒　ＭＳの最適値の上界 各ブール変数 ai を確率 xi*で真とする．

z j z j * （x*，ｚ*）線形緩和問題の最適解． 各ブール変数 ai を確率 xi*で真とする． 真となるクローズ重みの総和の期待値 ランダム化算法（定義) （x*，ｚ*）線形緩和問題の最適解． 各ブール変数 ai を確率 xi*で真とする． 真となるクローズ重みの総和の期待値 　　= ｊ＝１ ｍ i ∈cｊ ∑w j （1- Π x*[i］） z j [i ]= i +n (i =1,...,n) i ｰn (i = n+1,...,2n) |C j |=k　ならば，1- Π x*[i]≧ i ∈cｊ １‐(1‐１/ｋ　)ｋ 補題： z j *

1- Π x*[i]≧1‐ （∑ （ 1‐ x*i ）/ｋ） 補題の証明 |C j |=k　ならば，1- Π x*[i]≧ i ∈cｊ １‐(1‐１/ｋ　)ｋ 補題： 証明： 　　相加相乗平均より， 1- Π x*[i]≧1‐ （∑ （ 1‐ x*i ）/ｋ） 　　　　　　　　≧ 1‐（１‐ /ｋ）ｋ 　z*j　の関数　1‐（１‐ z*j /ｋ）　の凹性より ≧ 1‐（１‐1/ｋ） 　 z j * ｋ i ∈cｊ i ∈cｊ Z*j ｋ ｋ　 z* j

∑ ∑ w j （1- Π x*[i］） ≧∑ ∑ w j z j ≧(線形緩和の最適値) ≧(MAX k’SATの最適値) （１‐（1‐１/ｋ　)ｋ)近似解法 真となるクローズの重みの和の期待値は？ 　Γk　:リテラルをｋ個含むクローズの集合． MAX k’SATならば， i ∈cｊ ∑　∑　w j （1- Π x*[i］） k＝１ ∞ cｊ∈　Γk ≧∑　∑　w j z j k＝１ ∞ cｊ∈　Γk （１‐（1‐１/ｋ　)ｋ) ≧(線形緩和の最適値) （１‐（1‐１/ｋ’　)ｋ’ ) ≧(MAX k’SATの最適値) （１‐（1‐１/ｋ’　)ｋ’ )

≧(MAX k’SATの最適値) MAX k’SATならば， 期待値 （１‐（1‐１/ｋ’ )ｋ’ ) 0.632近似解法 MAX k’SATならば， 期待値 ｋ’ 　　（１‐（1‐１/ｋ’　)ｋ’ ) １　　1 ２ 3/4=0.75‥ ３ 19/27=0.703‥ ４ 175/256=0.684‥ ∞　　1－1/e＝0.632‥ ≧(MAX k’SATの最適値) （１‐（1‐１/ｋ’　)ｋ’ )

[Goemans and Williamson 94] ●1/2近似解法 と 0.632近似解法を 組み合わせる． MAX SATの3/4 近似解法 [Goemans　and Williamson 94] ●1/2近似解法 と 0.632近似解法を 　　組み合わせる．

リテラルを k’個含むクローズならば， 1/2近似解法： 真となる確率≧（１‐（1/2)ｋ’ ) 1/2近似解法と0.632近似解法 リテラルを k’個含むクローズならば， 1/2近似解法： 真となる確率≧（１‐（1/2)ｋ’ ) .632近似解法：真となる確率≧（１‐（１‐１/ｋ’)ｋ’ ) ｋ’ 　　（１‐（1‐１/ｋ’　)ｋ’ ) （１‐（1/2)ｋ’ ) １　　1 1/2 ２ 3/4=0.75‥ 3/4=0.75 ３ 19/27=0.703‥ 7/8=0.875 ４ 175/256=0.684‥ 15/16=0.9735 ∞　　1－1/e＝0.632‥ 1

が成り立つ． ≧ (MAX SATの最適値) (3/4) 4/3近似解法 1/2近似解法と 0.632 近似解法のうち一方を 　　確率(1/2)で選んで実行する． 任意の正整数ｋ’に対し， [（１‐（1‐１/ｋ’　)ｋ’ )＋（１‐（1/2)ｋ’ )]/2≧3/4 　が成り立つ． 期待値≧ (MAX SATの線形緩和問題の最適値) 　　　　　　　　　　[（１‐（1‐１/ｋ’　)ｋ’ )＋（１‐（1/2)ｋ’ )]/2 　　　　≧ (MAX SATの最適値) (3/4)

( z1/2 +zLP)/2 ≦ max{z1/2,zLP} 4/3近似解法(実際） 4/3近似解法 1/2近似解法と 0.632 近似解法のうち一方を 　　確率(1/2)で選んで実行する． 　　　　　下の方が同じかより良い． 1/2近似解法と 0.632 近似解法の両方を 　　実行し良い方を選ぶ． z1/2 :1/2近似解法の期待値 zLP :0.632 近似解法の期待値 ( z1/2 +zLP)/2 ≦ max{z1/2,zLP}

脱ランダム化(derandomization)

a1 a2 a3が真となる確率( x,1/2,1/2) a1 a2 a3が真となる確率(1,y,1/2) 脱ランダム化 ｛ a2 } 　４ ｛ ￢a1， a2，￢a3 } 　１　 ｛ ￢a1，￢a2，￢a3 } ６　 ｛ ￢a1，￢a2， a3 } 　４　 ｛ a1，￢a2 } 　３　　 ｛ a1， a3 } ９　 a1 a2 a3が真となる確率( x,1/2,1/2) 期待値＝ 4(1-1/2)+ 1(1-(1/2)2(1-x)) +6 (1-(1/2)2 (1-x)) +4 (1-(1/2)2(1-x))+3 (1-(1/2) x)+9 (1-(1/2)x) =19+(13/4) x x=1とすれば、22.25 となる． a1 a2 a3が真となる確率(1,y,1/2) 期待値＝ 4y+ 1(1-(1/2)y) +6 (1-(1/2) (1-y)) +4 (1-(1/2) (1- y))+3 +9 =19+3.5y y=1とすれば、22.5 となる． a1 a2 a3が真となる確率(1,1,z) 期待値＝ 22+1(1-z) z=1とすれば、23 となる． - 重みの総和=２７ 1/2近似解法　 a1,a2,a3が真となる確率(1/2,1/2,1/2)　 期待値=20.6‥ = 4(1-1/2)+1(1-(1/2)3)+6 (1-(1/2)3) +4 (1-(1/2)3)+3 (1-(1/2)2)+9 (1-(1/2)2)

MAX CUTの近似解法

MAX CUT問題(問題例) カット重み=８　　　　　　　カット重み=１４ ５ ４ ３ ２ １ ４ ５ ３ ３ ２ １ ４ ５

ｶｯﾄの定義 グラフG=（V,E) 頂点集合U⊆V ５ ４ ３ ２ １ U V-U δ(U)：ｶｯﾄ w（U）：ｶｯﾄ重み14

MAX CUT問題 入力:無向グラフG=(V,E)，非負枝重みｗ:E→Z． 問題：G中のカットで， 重み最大となるものを求めよ． 　　 重み最大となるものを求めよ． 頂点部分集合U⊆V に対するカット： δ(U)=｛e∈E |e はU中の頂点とU に無い頂点を結ぶ｝ カットδ(U)の重さ： 　ｗ(U)= δ(U)中の枝重みの総和． MAX CUT問題：max {ｗ (U ) | U⊆V } 　　　　　　　　　　　　　　　　　　NP‐困難[ Karp 72]

MAX CUTの1/2 近似解法 ●非常に単純なランダム化算法．

MAX CUT問題：max {ｗ(U) | U ⊆V } １/２近似解法： 各頂点を１/２の確率でUに入れる． 解析：各枝について，両端の内 カットの重みの期待値ｚ は， ｚ　＝∑{　Pr[e 　がδ(U)には入る]ｗ　（e ）｜ e ∈E　} 　＝ ∑{　(1/2)ｗ　（e ）｜ e ∈E　} (枝重みの総和)≧(最大カットの重み)より， ｚ ≧ (1/2)*最適値

MAX CUTの0.878 近似解法 [Goemans and Williamson 95] ●MAX CUTを 　　非凸2次連続最適化問題に変形． ●半正定値計画緩和． ●ランダム化アルゴリズム．

入力:無向グラフG=(V,E)，非負枝重みｗ:E→Z， S：原点を中心とし，半径1/π の球の表面． (大円の半円弧の長さ=１) 球面配置問題 入力:無向グラフG=(V,E)，非負枝重みｗ:E→Z， S：原点を中心とし，半径1/π の球の表面． 　　(大円の半円弧の長さ=１) ∀v,∀v’∈ S , 　　ｄ(vv’)= v と v’を結ぶ円弧の短い方の長さ． 球面配置問題 グラフGの頂点をS上に配置して， 　　枝重みと距離の積の総和を最大化する． max{∑ｗ　 (i,j) ｄ(v(i )v( j)) | v(i )∈ S (∀ i ∈V )} {i,j }

max{∑ｗ (i,j) ｄ(v(i )v( j)) | v(i )∈S (∀i∈V)} 定理 δ(U*)：最大カット． 球面配置問題(定理) max{∑ｗ　 (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)) ｄ(v’(i )v’( j)) i 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{∑ｗ (i,j) ｄ(v(i )v( j)) | v(i )∈S (∀i∈V)} 定理 δ(U*)：最大カット． 球面配置からのｶｯﾄ生成 max{∑ｗ　 (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 )は球面配置問題の最適解． 任意の球面配置vに対し， 原点を境界に含む閉半空間全てを 等確率で発生させる事により， vの目的関数値∑ｗ　 (i,j) ｄ(v(i )v( j)) 以上のカットを生成する事が出来る． {i,j } H {i,j }

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’） 1/π 1/2 d S

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 }

v’ がカット配置⇔∀i,∀j,ｄ(v(i )v( j))は0または1 ⇔ ∀i,∀j, f(v(i )v( j))は0または1 なぜ緩和問題になっているのか？ カット配置 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 }

∀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∑w (i,j) ｆ(v’(i )v’( j)) ≧0.878∑w (i,j) ｆ(v*(i )v*( j)) 最適値の比率 定理　v’(i ):緩和問題の最適解. (最大カット重み)≧(配置v’(i )の目的関数値) 　≧0.878（球面配置問題の最適値）=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 }

[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)} 　　　 　　||　（実はこの２つの問題は等しい） 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 }

[Goemans and Williamson 95] ●MAX ２SATを 制約付MAX CUT問題に変形する．

制約付MAX CUT問題 入力:無向グラフG=(V,E), 枝集合E’, 非負枝重みｗ: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問題 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

おしまい

現在までの結果 MAX SAT 0.770 [Asano 97] MAX 2SAT 0.931 [Feige and Goemans 95] MAX 3SAT 0.875 [Karloff and Zwick 97] MAX 3SAT問題に近似比率0.875より良い 　　　多項式時間算法が存在するならば、P=NP.