Approximation of k-Set Cover by Semi-Local Optimization Rong-chii Duh, Martin Fürer In Proceedings of the 29th Annual ACM Symposium on Theory of Computing,1997, pp.256-264 中央大学大学院 理工学研究科 情報工学専攻 浅野研究室 ◎堀 邦彰 黒岩 健二 山下 慶子

k-Set Cover Problem 入力：集合 U 上の部分集合の集まり C ただし各部分集合のサイズは高々 k 部分集合の和は U |U | = n 出力：和集合が U となるような最小の部分集合の集まり 3-Set 2-Set k-Set Cover Problem

仮定： 任意の部分集合はその中のさらに小さな 部分集合をすべて含んでいる Disjoint k-Set cover problem と考えることができる 選ばれた部分集合は共通部分を持たない k-Set Cover Problem

k-Set Cover 問題について k-Set cover problem は k = 2 多項式時間で解ける Matching を利用 k ≧ 3 NP-complete Greedy algorithm，線形計画問題に緩和 局所改善法 などを利用 して近似 一般に，任意に固定したε> 0 に対して ( 1 －ε) ln n では近似できないといわれている k-Set Cover Problem

Algorithm for 2-Set Cover 最大マッチング k-Set Cover Problem

今までの研究 3-Set Cover に対する近似率 11/6 D.S.Johnson ( 1974 )，L.Lovász( 1975 ) 10/6 O.Goldschmidt, D.S.Hochbaum, And G. Yu ( 1993 ) 11/7 Magnus M. Halldórsson ( 1995 ) 7/5 Magnus M. Halldórsson ( 1996 ) Magnus の大域ステップに似た方法で近似比 4/3 k-Set Cover Problem

Semi-Local Optimization 目的関数 １） U をカバーする部分集合の集まりを最小化する ２） 1-Sets の数を減らす k-Set Cover Problem

Semi-Local Optimization for 3-Set Cover 1) greedy algorithm により実行可能解を求める 2) semi-local (2,1)-improvement を可能な限り行なう 2個までの 3-Sets の挿入と現在のカバーからの 1個までの 3-Sets の削除を行なう ① ② 3-Sets でカバーされていないU上の要素を マッチングを用いてカバーする 局所ステップ 大域に変化を与える k-Set Cover Problem

具体例 Greedy Algorithm semi-local(0,1)improvement k-Set Cover Problem

アルゴリズムの解析 解析のために 1) 比較グラフを用いる アルゴリズムによって求められた解と 最適解とを比較するグラフ 2) 補助グラフを用いる 求められた解の一部と最適解とによって 構成されたグラフ k-Set Cover Problem

比較グラフ q1 q2 q3 p1 p2 p3 p4 アルゴリズムによって 求められた解 = A 最適解 = B A={A1 , A2 , A3} A1={p4}, A2={p4} A3={p1 , p2} p1 p2 p3 p4 q1 q2 q3 比較グラフ B={B1 , B2 , B3} B1=φ, B2= φ B3={q1 , q2 , q3} k-Set Cover Problem

補題 2.1 3-Set Cover に対する Semi-Local (2,1)-optimization algorithm は a1+2a2+3a3 = b1+2b2+3b3 = u の解を生成する ここで | Aj | = aj , | Bj | = bj , | U | = u とする p1 p2 p3 p4 q1 q2 q3 比較グラフ 証明： 比較グラフの構成 方法より明らか k-Set Cover Problem

補題 2.2 3-Set Cover に対する Semi-Local (2,1)-optimization algorithm は a1≦ b1 の解を生成する 証明： A1 を含む任意の連結成分は A3を同じ連結成分内に含むことはできない．なぜなら，A1からいくつかの A2を通って A3に至る任意のパスPは Semi-Local (0,1)-improvement を導くからである． k-Set Cover Problem

Semi-Local(0,1)-improvement (0,1) 改善後 パス P 求められた解 最適解 比較グラフ すべての改善を行なった はずなのでこのような改善は 行なえないはずである k-Set Cover Problem

A1 からはじめてこの連結成分内の他のすべての頂点を 始点からの距離によってクラス分けを行なう． A1とA3は同じ連結成分内にはない A1 からはじめてこの連結成分内の他のすべての頂点を 始点からの距離によってクラス分けを行なう． 距離2d のすべての A の頂点には唯一，距離2d+1の 隣接している B の頂点がある． A1 を root とする木が構成でき，そのすべての葉はB1となっている マッチングの最大性に反する (1,0) 改善 可能 a1≦b1 k-Set Cover Problem

補助グラフ G=(B, AｰA3) p1 p3 p4 p5 p2 q1 q2 q3 q4 求められた解 最適解 p6 p1 p3 p4 p6 k-Set Cover Problem

補題 2.3 3-Set Cover に対する Semi-Local (2,1)-optimization algorithm は a1+ a2 ≦ b1 + b2 + b3 の解 A を生成する 証明： 補助グラフ G において補助グラフの連結成分は 2 つ以上の閉路を含むことはできない． なぜなら Semi-Local (2,0)-improvement ( または (1,0) ) を 導くからである． k-Set Cover Problem

Semi-Local(2,0)-improvement 3-Set 求められた解 最適解 補助グラフ (2,0)改善後 すべての改善を行なった はずなのでこのような改善は 行なえないはずである k-Set Cover Problem

枝の本数は高々補助グラフの頂点の数に 等しいくらいしかない． 枝はアルゴリズムによって選ばれた 1-Sets と 2-Sets をあらわしており 頂点は最適解の集合をあらわしている a1+a2 ≦ b1+b2+ b3 k-Set Cover Problem

定理２.１ 3-Set Cover に対するSemi-Local (2,1)-optimization algorithmは, 3a≦4b－b1－b2の解Aを生成する ここで | A | = a , |B| = b とする 証明： 補題２.１の等式と補題２.２, ２.３の不等式とを加える ことによって, a1+2a2+3a3＝b1+2b2+b3 a1≦b1 a1+a2≦b1+b2+b3 3(a1+ a2+a3) ≦3b1 +3 b2+4b3 したがって、 3a≦4b－b1－b2 + ) k-Set Cover Problem

定理 2.2 3-Set Cover に対するSemi-Local (2,1)-optimization algorithm は, 近似比 4/3の解を生成する 証明： 定理２.１より 3a≦4bｰb1ｰ b2≦4b ∴ a / b≦ 4/3 k-Set Cover Problem

Semi-Local Optimization for k-Set Cover s 個までのk'-Sets(3≦k'≦k)の挿入と, 現在の カバーからの t 個までのk'-Setsの削除を行う ① ② k'-SetでカバーされていないU上の要素を マッチングを用いてカバーする 3-Set Coverの場合と同様に、次の等式と不等式を得る k-Set Cover Problem

k-Set Cover に対する Semi-Local (2,1)-optimization algorithmの近似率は である. 前の等式と不等式を加えると、 k-Set Cover に対する Semi-Local (2,1)-optimization algorithmの近似率は である. k-Set Cover Problem

Greedy V.S. Semi-Local k に対する近似率 6 を超えない k に対しては, Semi-Local optimization algorithm が greedy algorithm よりも近似率の点で 優れている. k が大きいところではGreedy アルゴリズムを用い， k が 小さくなったら Semi-Local を 用いる k-Set Cover Problem

Greedy-SLI k,l (U,C ) Greedy Phase: ｆｏｒ j ← k downto l +1 do gｒｅｅｄｙ に j-Sets の極大集合を選ぶ Semi-Local Improvement Phase for Smaller Sets: U内のまだカバーされていない要素上で Semi-Local optimization を行なう 定理3.1 Greedy-SLI k,l アルゴリズムは k-Set Cover Problem に対し、近似率 Hk － 5/12 の解を生成する （ただし， l＝４で k≧４である）（Hk：調和数） k-Set Cover Problem

3-Set Cover に対するアルゴリズム同様， k-Set Cover の Greedy Phase においても， 1-Sets の数を減らすように考慮する． Greedy Phase において極大集合を選ぶ際 1-Sets が増加しないならばその集合を選ぶ k-Set Cover Problem

Restricted_Greedy-SLIk,l (U,C ) Greedy Phase: ｆｏｒ j ← k downto l +1 do Greedy に j-Sets の極大集合を選ぶ Restricted Phase: ｆｏｒ j ← l downto 4 do j-Sets の選択が1-Setsの数を増やさないような 場合に制限して j-Sets の極大集合を選ぶ SLI Phase for 3-Set Cover : U内のまだカバーされていない要素上で Semi-Local optimizationを行う k-Set Cover Problem

定理3.2 k-Set Cover の Restricted_Greedy-SLIk,l の近似率は， k=5かつ l＝5 あるいは k=4 かつ l=4 に対し，高々 Hk － 1/2 となる k-Set Cover Problem

Color Saving Color Savingとは… 目的 相補目的関数を用いて、最小の色数でグラフを 着色する問題. ( n 頂点のグラフを着色するのに n 色があると仮定) 目的 何色が使われていないか[n－(使われた色の数)]を数える. 目的関数は,サイズ j の{0,1}集合 Aj に対して である k-Set Cover Problem

k-Set Cover Problem

Color Saving は Set-Cover problem となる。 グラフの独立集合を Sets とすると， Color Saving は Set-Cover problem となる。 k-Set Cover Problem

定理4.1 定理 4.2 Semi-local(2.1)-optimization アルゴリズムは， サイズ 3の最大独立集合を持つグラフに対し， 近似率 6/5 の Color Saving Problem の解を 生成する 定理 4.2 Color Saving Problemの近似率は，高々 である k-Set Cover Problem

問題点 近似アルゴリズムの解析が主であり，アルゴリズムの詳細がはっきりとは述べられていない． Semi-Local improvement の順序? また，効率的な順序は? 計算量は? Color Saving において極大集合をすべて求めて おかなければならないのか? 実装化の複雑さ k-Set Cover Problem