近似アルゴリズム第19章多分割カット

近似アルゴリズム第１９章
多分割カット
東北大学大学院情報科学研究科
M1 鈴木晶子
発表の流れ
•
•
•
•
•
多分割カット問題とその定式化
多分割カット問題に対するLP-緩和
乱数使用ラウンディングアルゴリズム
多分割カット問題の一般化…点型多分割カット問題
点型多分割カット問題の半整数性
2015/10/1
多分割カット問題
• 入力
– ターミナルの集合 S  {s1 , s2 ,, sk }  V が付随する無向グ
ラフ G  (V , E )
– 辺に付随する重み関数 w : E  R 
• Gに対する多分割カット
– 辺の部分集合で、
除去するとターミナルが
それぞれ異なる連結成分に
属するようになるもの
s2
s1
2
1
1
2
2
2
2
1
1
3
2
1
s3
多分割カット問題：最小重みの多分割カットを求める問題
2015/10/1
問題の定式化
最小化
c d
d 1
eE
制約式
e p
e
e
e
( p P)
d e {0, 1} (e  E )
• de : 0/1変数
辺e∈Eが多分割カットに選ばれるとき1となる
• ce : 辺eの重み
• P : 異なるターミナル間を結ぶ全てのパスの集合
2015/10/1
多分割カット問題のLP-緩和
•  k ：k-1次元の単体
– R k 空間内で {x  R k | x  0かつi xi  1} と定義
( xi は点x のi番目の座標値 )
– k-1次元の凸多面体
• 例： 3
(0,0,1)
(0,1,0)
(1,0,0)
2015/10/1
どのように緩和するのか？
• Gの各点を単体  k の点に写像する
• k個のターミナルは、それぞれ単体の異なる頂点に写
像される
• その他の点は、単体  k 内のどこかに写像される
• 例： 3
(0,0,1)
s1
2
1
1
s2
2015/10/1
2
2
2
2
1
1
3
2
1
(0,1,0)
s3
(1,0,0)
xu=(0.5,0.1,0.4)
u
v
d(u, v)
xv=(0.5,0.5,0)
d(u,v)=1/2(|0.5-0.5|+|0.1-0.5|+|0.4-0|)=0.4
• xv  k を点vが写像される点とする。
• 辺(u, v)∈Eの長さd(u, v)を、xuとxvのl1-距離の1/2倍と
して定義する。
k
1
i
i
d (u, v)   xu  xv
2 i 1
多分割カット問題のLP-緩和
緩和(19.1)
 c(u, v)d (u, v)
最小化
( u ,v )E
1 k i
i
d (u, v)   xu  xv
2 i 1
xv   k
xsi  ei
制約式
((u, v)  E )
(v  V )
( si  S )
•  k  {x  R | x  0かつi x  1}
k
i
: e  R , x  1かつx  0( j  i)
• e　i
i
k
i
j
（第i 座標の単位ベクトル）
2015/10/1
例題19.2
Δ3への写像
（最小小数多分割カット）
もとのグラフ
s1
s1
2
s2
(0.5, 0.5, 0)
u
v
2
2
1
2
1
(0, 1, 0)
1
w
2
s3
最適整数解のコスト
=2+1+2+1+2
=8
2015/10/1
1
1
2
1
u
(1, 0, 0)
s2
0.5
0.5
1
(0.5, 0, 0.5)
w
v
1
0.5
(0, 0.5, 0.5)
(0, 0, 1)
1
s3
最適小数解のコスト
=（2点間の距離×辺のコスト）の合計
=(2×0.5)×6+(1×0.5)×3
=7.5
補題19.3
xを緩和(19.1)の実行可能解とする。
一般性を失うことなく、各辺(u,v)∈Eに対して、xuとxvは
高々2つの座標値のみ異なると仮定できる。
[証明]
最小小数解のコストを変えずに、
辺に点を加えて分割していく。
………
2015/10/1
補題19.3の証明
• 2点が3個以上の座標で異なるような辺(u,v)∈Eを考え
る
(u , v )
xu
xv
3個以上の座標値が異なっている
• この辺を、点wを用いて2つの新しい辺でおきかえる
(u, w)
(w, v)
xw
xu
xv
• ただし、新しくできた辺のコストはc(u,v)と等しいとする
– つまり、c(u,v) = c(u,w) = c(w,v)
⇒最適整数解のコストは不変
2015/10/1
補題19.3の証明
• 新しくできた辺のコストはc(u,v)と同じ
• 最小小数解のコストが不変であるためには、この条件
に加えて
d (u, v)  d (u, w)  d ( w, v)
である必要がある
（LP-緩和解のコストはc(u,v)d(u,v)の総和であるため）
d (u, v)  d (u, w)  d ( w, v)が成り立つように
xwの座標値を設定する
2015/10/1
xuとxvで値が異なる座標を考える。
値が異なる座標の中で、差が最も小さい座標を第i 座標
とする。
1
i
j
k
xu  ( xu ,, xu ,, xu ,, xu )
差α（最小）
差α以上、
xuj  xvj
xv  ( x ,, x ,, x ,, x )
1
v
i
v
j
v
i
i
と仮定し、
x x
  xv  xu とおく。
xuとxvは
– 3個以上の座標で値が異なり
– 第i 座標で値の差が最小
– xui  xvi かつ  xul   xvl  1
i
u
k
v
i
v
l
l
なので、 xuj  xvj   となるような座標 j が存在する。
そこで、xwを以下のように定める。
xu  ( x ,, x ,, x ,, x )
1
u
i
u
j
u
k
u
xwi  xui
xw  ( x ,
, x ,,
,,xx 
,
x ), x )
, 
x  x 
xv  ( x ,, x ,, x ,, x )
残りの座標は
xvと同じ
1
w
v
ii
uw
1
v
i
v
jj
vw
j
v
k
w
k
v
k
v
xui  xvi  より…
x
l
l
w
 1  xw   k
d (u, v)  d (u, w)  d (w, v)
j
w
j
v
xu  ( x ,, x ,, x ,, x )
1
u
i
u
j
u
k
u
xw  ( xv1 ,, xui ,, xvj   ,, xvk )
xv  ( xv1 ,, xvi ,, xvj ,, xvk )
• uとwの間で異なる座標値の数は、uとvよりも少なくなる
• vとwの間で異なる座標値の数は、i とj の2つのみ
Eの各辺は、高々k-2回の分割を行えば
異なる座標値の数が2つ以下になる！
乱数使用ラウンディングアルゴリズム
• 補題19.3の性質を満たす緩和(19.1)の最適解を用い
て、多分割カットを求める
• 全体の点の集合Vを、k個の集合V1,…,Vkに分割する
• si∈Viとなるように分割する
s
s
1
1
V1
s2
s3
s2
V2
• 異なる集合間にまたがる辺⇒多分割カット
2015/10/1
V3
s3
準備(1)
• x : 緩和(19.1)の最適解
（補題19.3の性質を満たすものとする）
• Ei : Ei  {(u, v)  E | xui  xvi }
– 両端点のi 座標が異なる辺からなる集合
– 長さ非零の辺は、異なる2つの集合に含まれる
• Wi : Wi   c(e)d (e)
eEi
– Wkが最大となるようにターミナルの番号をつけ直す
2015/10/1
準備(2)
• B(si,ρ) : ρ∈(0,1)に対して、
B(si ,  )  {v V | xvi  }
– 第i 座標に直行射影したとき、ei (si が写像される点)からの
距離が1-ρ以下になる点の集合
• 例：ρ＝1/3のときのB(s1,ρ)
s3
(0,0,1)
(1/3,0,0)
(0,1,0)
(1,0,0)
2015/10/1
s
s
1
2
アルゴリズム19.4(多分割カット)
1. 緩和(19.1)の最適解xを計算する
2. W1,…,Wkのなかで、Wkが最大になるようにターミナ
ルの番号を付け替える
s1
s1
2
1
u
1
2
v
1
w
(0, 1, 0)
2
s3
s2
W1= 5
2015/10/1
(0.5, 0, 0.5)
(0.5, 0.5, 0)
u
2
2
s2
2
(1, 0, 0)
v
w
(0, 0.5, 0.5)
W2= 5
(0, 0, 1)
s3
W3= 5
アルゴリズム19.4
3. ρ∈(0,1)とσ∈{(1,2,…,k-1,k), (k-1,k-2,…,1,k)}を一様
にランダムに選ぶ。
4. i=1から1ずつ増加しながら、k-1まで以下を繰り返す
V (i )  B(s (i ) ,  )   j i V ( j )
手順3のσで選んだ順にVi を決めていく
 第i 座標に全ての点を直交射影したとき、
si から1-ρ以下の距離にある点（の集合）をVi とする
 ただし、一度集合Vi の要素となった点は2度以上選ばない

5. Vk  V   ik Vi

2015/10/1
最後に、一度も選ばれなかった点の集合をVkとする
アルゴリズム19.4
ρ=0.4, σ=(2,1,3)とする
s1
(0.5, 0.5, 0)
u
(0, 1, 0)
s2
V2
多分割カット
(1, 0, 0)
V1
(0.5, 0, 0.5)
w
V3
v
(0, 0.5, 0.5)
(0, 0, 1)
s3
6. CをV1,…,Vkの異なる集合間にまたがる辺全体とし、
Cを出力する。
2015/10/1
定理19.7
多分割カット問題に対して、3/2近似を達成する乱数
使用近似アルゴリズムが存在する。
この定理を証明するために、
アルゴリズム19.4で得られる多分割カットのコストの
期待値E[c(C)]が
E[c(C )]  (1.5  1 )OPTf
k
という不等式を満たすことを示す。
（ただし、OPTf は最適小数解のコストを表す）
2015/10/1
補題19.5
Ei を、 Ei  {(u, v)  E | xui  xvi } を満たす辺の集合
（両端点のi 座標が異なる辺からなる集合）とする。
このとき、
e∈E-Ek ならばPr[e∈C]≦1.5d(e)であり、
e∈Ek ならばPr[e∈C]≦d(e)である。
2015/10/1
補題19.5の証明
• e=(u,v)とする。
• アルゴリズム19.4において、Vをk個の集合V1,…,Vkに
分割したとき、xuとxvが異なる集合に含まれる場合を
考える。
[e∈E-Ek の場合]
– xuとxvで値が異なる座標は、i 座標とj 座標であると
する
– 対称性より、 xui  xvi , xvj  xuj , xui  xvj とする
2015/10/1
i
u
i
v
j
u
j
v の配置は以下の場合が
このとき、 x , x , x , x
考えられる。
i
i
j
j
[
x
,
x
]
[
x
,
x
《case1 : 区間 u v と v u ]が共通部分を持たない場合》
α
0
β
xui
xvi xvj
i
i
j
xuj
1
j
《case2 : 区間 [ xu , xv ]と [ xv , xu ]が共通部分を持つ場合》
α
0
i
u
x
β
j
v
x
i
v
x
j
u
x
ここで、区間α，βを上図のように定義する。
1
α
0
i
u
β
i
v
j
v
x x
x
α
0
i
u
x
j
u
1
j
u
1
x
β
j
v
x
i
v
x
x
• i, j以外の座標値はxu,xvともに等しい。
したがって、Vi , Vj 以外の集合Vl にxu,xvのどちらか
一方が含まれる場合、もう一方の点もVl に含まれる。
• xu,xvが同じ集合に含まれるのは、
ρ=[0,1]-(α∪β), つまりρが区間α，β以外の区間
に含まれている場合である。
α
0
i
u
β
i
v
j
v
x x
x
α
0
xui
j
u
x
1
xuj
1
β
xvj xvi
辺eがカットに含まれる、つまり、
uとvが異なる集合に含まれる可能性があるのは…
1. ρが区間βに含まれるとき
2. ρが区間αに含まれていて、
かつσ( i )＜σ( j )のとき
（つまりVi のほうがVj より先に決定されるとき）
その確率は、 xvi  xui  xuj  xvj  d (e) より
Pr[e  C ]   

2
 1.5d (e)
[e=(u,v)∈Ekの場合]
– xuとxvで値が異なる座標は、i 座標とk座標である
とする
α
0
β
xvi xvk
xui
α
0
i
u
x
xuk
1
k
u
1
β
k
v
x
i
v
x
x
– Vkはρの値に関係なく、Vk=V-(V1∪…∪Vk-1)と
決定される
– uとvが異なる集合に含まれる可能性があるのは、
ρが区間αに含まれているとき
よって、
Pr[e  C ]    d (e)
（証明終）
補題19.6
アルゴリズム19.4で出力された多分割カットCは
以下の不等式を満たす。
E[c(C )]  (1.5  1 )OPTf
k
2015/10/1
補題19.6の証明
• OPTf は最適小数解のコストであり、
OPTf  e c(e)d (e) と表される。

• Wi は、両端点のi 座標が異なる辺の集合Ei に対し
Wi   c(e)d (e) と表される。
eEi
• 長さ非零の辺は、2つの集合Ei に含まれるので
k
W  2  OPT
i 1
i
f
• WkはW1,…,Wkの中で値が最大となるものなので
2
Wk   c(e)d (e)   OPTf
k
eEk
2015/10/1
補題19.6の証明
したがって、
E[c(C )]   c(e) Pr[e  C ]
eE

 c(e) Pr[e  C ]   c(e) Pr[e  C]
eE  Ek
補題19.5より
E[c(C )]  1.5
eEk
 c ( e ) d ( e )   c ( e) d ( e)
eE  Ek
eEk
 1.5 c(e)d (e)  0.5  c(e)d (e)
eE

eEk
2  OPT より、 E[c(C )]  (1.5 
c
(
e
)
d
(
e
)

f
eEk
k
1 )  OPTf
k
（証明終）
2015/10/1
定理19.7の証明
演習問題19.4
• 定理19.7
多分割カット問題に対して、3/2近似を達成する乱数使用近
似アルゴリズムが存在する。
• アルゴリズム19.4を多項式回数走らせ、最善のカット
を出力することにする。
• このとき、得られたカットのコストc(C)に関して
c(C)  1.5  OPTf
が高い確率で成り立つことを示す。
2015/10/1
定理19.7の証明
• 補題19.6より、 Pr[c(C )  1.5  OPTf ]  2 k  2 n
• アルゴリズム19.4を多項式回数走らせたとき、
c(C)  1.5  OPTf が成り立つ確率を
Chernoff限界を用いて求める。
2015/10/1
Chernoff限界（p.363,付録B.2参照）
• n回のPoisson試行を0/1ランダム変数X1,…,Xnで表
す
• 0と1はそれぞれ成功・失敗を表す
• 1≦ i ≦nに対して0＜pi＜1で、 Pr[X i  1]  pとする
i
• ランダム変数 X  X1   X n とし、
n
  E[ X ]  i 1 pi とする
• 0＜δ≦１と仮定すると、以下の式が成り立つ。
(   2 / 2)
Pr[X  (1   ) ]  e
2015/10/1
定理19.7の証明
• アルゴリズム19.4を１回走らせ、解のコストc(C)が
c(C)  1.5  OPTf なら成功、 c(C)  1.5  OPTf なら失
敗とする
• すると、 Pr[X i  1]  2 が成立
n
• アルゴリズムは多項式回数走らせるので、 O(nd ) 回
（dは定数）走らせるとする
• このとき成功した回数の期待値E[X]について
  E[ X ]  O(n d )  2 n  O(n d 1 )
が成立する
2015/10/1
定理19.7の証明
•   1 1
(   2 / 2)
として Pr[X  (1   ) ]  e

Pr[X  1]  e
(  1)2 / 2 
e
に代入
O( nd 1 )
• よって、少なくとも1回は成功する確率は
Pr[X  1]  1  e
O( nd 1 )
(dは定数)
となり、高い確率で c(C)  1.5  OPTf が成立すると
いえる。
2015/10/1
点型多分割カット問題
• 入力
– 連結な無向グラフG=(V,E)
– 点に付随するコスト関数 c : V→R+
– ターミナル集合S={s1,s2,…,sk}⊆V
• Gに対する点型多分割カット
– V-Sの部分集合で、除くと
各ターミナルが互いに
非連結になるようなもの
3
s1
1
2
2
1
s2
2
〔点型多分割カット問題〕
コスト最小の点型多分割カットを求める問題
2015/10/1
s3
問題の定式化
最小化
c d
d 1
vV  S
制約式
v p
v
v
v
( p P)
d v {0, 1} (v V  S )
• dv : 0/1変数
点v∈V-Sが多分割カットに選ばれるとき1となる
• cv : 点vのコスト
• P : 異なるターミナル間を結ぶ全てのパスの集合
2015/10/1
問題のLP-緩和
LP-緩和(19.2)
最小化
c d
d 1
vV  S
制約式
v p
v
v
v
( p P)
d v  0 (v  V  S )
• dv : 距離ラベル
• パスの長さ：そのパスに含まれる、ターミナルでない
点の距離ラベルの和
s
1
0.6
0.5
0.2
s
2
s1とs2を結ぶ
=1.3
パスの長さ
• 2点間の距離：2点を結ぶ最短なパスの長さ
2015/10/1
点型多分割カット問題の双対問題
双対問題
LP-緩和(19.2)
最小化
c d
d 1
vV  S
制約式
v p
v
v
最大化
v
f
pP
( p P)
d v  0 (v  V  S )
制約式
p
f
p:v p
p
 cv (v  V  S )
f p  0 ( p P)
• fp : 異なるターミナル間を結ぶパスpに沿って流れる
フローの流量
• この双対問題は、最大多品種フローを求める問題と
解釈できる。
2015/10/1
相補条件
• d : LP(19.2)の最適解
• f : 双対LPの最適解
とする。相補条件より、
• 主相補条件
– 各 v  V  S に対して dv  0 ならば、vは飽和している。
つまり、多分割カットに選ばれる点を流れるフローの総量が
点のコストに等しくなる。 (
f p  cv )
• 双対相補条件
p:v p
– 各パスp∈Pに対して f p  0 ならば、pの長さはちょうど1で
ある。 (
d v  1)
p:vp
2015/10/1
領域Sと境界B
• 点v∈V-Sにdで表される距離ラベルが付随していると
する。
• 領域Si : 各ターミナルsi に対して、si から長さ0のパス
で到達可能な点の集合(si ∈Si とする)
• 境界Bi : Si に隣接する、Si 以外の全ての点の集合
S1
s1
0
1
0
0.5
B1
S3
0
B3
B2
1
1
2015/10/1
s3
0.5
s2
S2
主張19.9
i ≠j に対して、v∈Bi ∩Bj ならばdv =1である。
[証明]
si
Si
v
Sj
sj
• Si ,Sj に含まれる点の距離ラベルは全て0
• si とsj を結ぶパスのうち、パス上の正のコストの点がvのみで
あるようなパスが存在する
• LP-緩和(19.2)の制約式  dv  1 ( p  P )より、各ター
v p
ミナル間の距離は1以上でなければならない
よって、dv =1
2015/10/1
（証明終）
境界の分類
• M : 境界B1,…,Bk に含まれる点の集合
とする。このとき、集合Mを2つの集合に分割する。
• Mint : 2つ以上の境界に含まれる点の集合
• Mdisj : 1つの境界のみに含まれる点の集合
S3
B3
S1
B1
: M int
: M disj
B2
S2
2015/10/1
点型多分割カット問題の半整数解
•
•
•
•
ここで、LP(19.2)の最適解dから、以下のようにして半
整数解を得る。
int
disj
dから、 M と M に属する点をそれぞれ求める。
M int の各点に距離ラベル1を与える。
M disjの各点に距離ラベル1/2を与える。
残りの点には距離ラベル0を与える。
こうして得られた半整数解hが、LP(19.2)の最適解と
なることを示す。
2015/10/1
補題19.10
pは2つの異なるターミナル間のパスでfp＞0であるも
のとする。
int
このとき、pで使用されるMの点は、 M の点ならば
ちょうど1点からなり、 M disjの点ならばちょうど2点から
なる。
したがって、いずれか一方だけが成立する。
Si
si
si
2015/10/1
Si
v  M int
v1  M disj
Sj
v2  M disj
sj
Sj
sj
補題19.10の証明
int
pで使用されるMの点が M の点ならば、ちょうど1点
からなることの証明
• 双対相補条件より、 f p  0 なのでpの長さは1
int
M
• 主張19.9より、
の点の距離ラベルは1
• よって、この点以外にMの点を含むことはできない
2015/10/1
補題19.10の証明
disj
pで使用されるMの点が M の点ならば、ちょうど2点
からなることの証明
• pが M disj の点を3点以上含んだとする。
• pをsi からsj へと行くパスとし、
– u,w : p上の M disj に含まれる最初の点と最後の点
– v : p上のそれら以外の任意の
sk
M disj の点
Sk
とする。
si
2015/10/1
Si
v  M disj
p
u  M disj
w M disj
Sj
sj
sk
q
si
Si
Sk
v
u
path1
p
w
Sj
sj
path2
qを、vからSkの点のみを経由してskに行くパスとする。
ここで、2つのパスを考える。
– path1 : si からvに向かうpのパス + q
– path2 : qを逆にしたもの + vからsj に向かうpのパス
sk
q
si
Si
Sk
v
u
p
path1
w
Sj
sj
path2

path1,path2の少なくとも1つは、異なるターミナル間を結ぶ
正しいパスになっている。

その正しいパスは、正の距離ラベルをもつ点がpより1個以上
（少なくともuあるいはwの分だけ）少なくなっている

相補双対条件よりpの長さは1なので、path1,path2は
距離が1未満になってしまう⇒最適解dの条件に矛盾
したがって、補題19.10が成立。
（証明終）
補題19.11
hは、 M int の各点に1を、 M disj の各点に1/2を、残り
の各点に0を、それぞれ距離ラベルとして与える
LP(19.2)の解であるとする。
このときhは、LP(19.2)の最適解である。
[証明]
ターミナルsi からsj へ向かうどの正しいパスpも、2つの境界集
合Bi とBjの点を含む。
このパスpがv∈Bi ∩Bj となる点vを含む場合と含まない場合に
ついて、パスpの長さを考える。
si
2015/10/1
Si
Sj
v
p
sj
Si
si
v
Sj
sj
• パスpが点v∈Bi ∩Bj を含む場合
M int の定義より、v  M int である。
したがって、hv =1となる。
si
Si
Sj
• パスpが点v∈Bi ∩Bj を含まない場合
補題19.10より、パスpは M disj の2つの点を含む。
どちらの場合もpの長さは1以上になる。
したがってhは実行可能解である。
sj
次に、hの最適性を示す。
非零フローf に用いられるパスを、2つの集合に分ける。
sk
si
Si
Sk
P1
P2
Sj
sj
P1 : M int の点を1個用いるパスからなる
P2 : M disjの点を2個用いるパスからなる
補題19.10より、この2種類のパスしか存在しない。
sk
si
Sk
P1
Si
P2
Sj
sj
主相補条件より、
（各 v  V  S に対して dv  0 ならば、vは飽和している）
Mの各点はf で飽和している。
P1,P2に含まれるパスで運ばれるフローの総量は、
P1 : vM in t cv
全体のフローは
1
P2 : vM disj cv
2
1
vM int cv  2 vM disj cv  vV S hv cv
より、hの目的関数値はf の目的関数値と等しい。
よってhは最適解である。
（証明終）
定理19.12
LP(19.2)は常に半整数解をもつ。
さらに、任意の最適解から半整数最適解が多項式時
間で得られる。
2015/10/1
2-2/k 近似アルゴリズム
1.
2.
3.
4.
5.
演習問題19.11
最後に、点型多分割カット問題に対する2-2/k 近似
アルゴリズムを示す。
LP(19.2)の解dを求める。
d によって表される距離ラベルから、グラフ上の各
点を M intと M disj とその他の点に分割する。
M int の各点に距離ラベル1を、 M disjの各点に1/2を、
残りの点に0を与える。
半整数解を切り上げる。ただし M disj に含まれる点
のうち、ある1つの領域Si に隣接する点のみ0とする。
得られたカットを出力する。
2015/10/1
演習問題19.11
タイトな例
s3
s2
2
1/2 →1
s1
1/2 →1
2
1/2 →1
2
1/2 →0
0
k 
2
• 最適半整数解のコスト
→1/2×2×k=k
• アルゴリズムから得られるコスト
→2×1×(k-1)=2(k-1)
2015/10/1
sk

Download Report