Approximation of k-Set Cover by Semi

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
semi-local(1,1)improvement
k-Set Cover Problem
semi-local(2,0)improvement
アルゴリズムの解析
解析のために
1) 比較グラフを用いる
アルゴリズムによって求められた解と
最適解とを比較するグラフ
2) 補助グラフを用いる
求められた解の一部と最適解とによって
構成されたグラフ
k-Set Cover Problem
比較グラフ
q1
p1
p2
q2
q3
p3
p4
アルゴリズムによって
求められた解 = A
最適解 = B
A={A1 , A2 , A3}
A1={p4}, A2={p4}
A3={p1 , p2}
p1
B={B1 , B2 , B3}
B1=φ, B2= φ
B3={q1 , q2 , q3}
p3
p2
p4
k-Set Cover Problem
q1
q2
q3
比較グラフ
補題 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
k-Set Cover Problem
q1
q2
q3
比較グラフ
補題 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
パス P
求められた解
最適解
比較グラフ
(0,1) 改善後
すべての改善を行なった
はずなのでこのような改善は
行なえないはずである
k-Set Cover Problem
A1とA3は同じ連結成分内にはない
A1 からはじめてこの連結成分内の他のすべての頂点を
始点からの距離によってクラス分けを行なう．
距離2d のすべての A の頂点には唯一，距離2d+1の
隣接している B の頂点がある．
A1 を root とする木
(1,0) 改善
マッチング
が構成でき，その
a1≦b1
可能
の最大性
すべての葉はB1と
に反する
なっている
k-Set Cover Problem
補助グラフ G=(B, AｰA3)
p1
p6
p2
p3
q1
p4
q2
p5
q3
q4
求められた解
最適解
p2
q1
p1
q2
p6
p3
q3
p5
p4
q4
補助グラフ
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
k
 ja   jb
j
j 1
j
j 1
a1  b1
k
a1  a 2   bj
j 1
k-Set Cover Problem
前の等式と不等式を加えると、
k
k
j 3
j 2
k
k
j 1
j 1
3a1  3a 2   jaj  3b1   ( j  1)bj
3 aj  ( k  1) bj

a k 1

b
3
k-Set Cover に対する Semi-Local (2,1)-optimization
k 1
algorithmの近似率は 3 である.
k-Set Cover Problem
Greedy V.S. Semi-Local
k に対する近似率
k
Greedy
Semi-Local
4
5
6
7
k
2.0830
2.2830
2.4500
2.5928
Hk
1.66
2
2.33
2.66
(k +1)/3
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 に対して
n
 ( j  1)a
j
j 2
である
k-Set Cover Problem
k-Set Cover Problem
グラフの独立集合を Sets とすると，
Color Saving は Set-Cover problem となる。
k-Set Cover Problem
定理4.1
Semi-local(2.1)-optimization アルゴリズムは，
サイズ 3の最大独立集合を持つグラフに対し，
近似率 6/5 の Color Saving Problem の解を
生成する
定理 4.2
Color Saving Problemの近似率は，高々 360
である
289
k-Set Cover Problem
問題点

近似アルゴリズムの解析が主であり，アルゴリズムの
詳細がはっきりとは述べられていない．
Semi-Local improvement の順序?
また，効率的な順序は?
計算量は?
Color Saving において極大集合をすべて求めて
おかなければならないのか?
実装化の複雑さ
k-Set Cover Problem

Download Report