Approximation of k-Set Cover by Semi-Local Optimization

Presentation on theme: "Approximation of k-Set Cover by Semi-Local Optimization"— Presentation transcript:

1 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 中央大学大学院 理工学研究科 情報工学専攻 浅野研究室 ◎堀 邦彰 黒岩 健二 山下 慶子

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

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

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

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

6 今までの研究 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

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

8 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

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

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

11 比較グラフ 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

12 補題 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

13 補題 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

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

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

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

17 補題 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

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

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

20 定理２.１ 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

21 定理 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

22 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

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

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

25 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

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

27 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

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

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

30 k-Set Cover Problem

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

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

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