スライド 1 - Tokuyama Laboratory

近似アルゴリズム
第24章施設配置
&
第25章 k-メディアン
徳山研究室 M1
鈴木晶子
発表の流れ
• Part1.施設配置
– 容量制限なしメトリック施設配置
– プライマルデュアル法に基づくアルゴリズム
– コストに関する定理
• Part2.k-メディアン
– メトリック k-メディアン
– 実行可能（小数）解を求めるアルゴリズム
– 乱数使用ラウンディング
– 近似率と計算時間
2
l
– 2 クラスタリング問題
Part1. 施設配置
容量制限なしメトリック施設配置
• 入力
– 2部グラフG
• 施設の集合F
• 都市の集合C
– 施設 i の開設コストfi
– 都市j の、施設i への接続（利用）コストcij
（接続コストは三角不等式を満たすものとする）
• 出力
– 開設する施設I⊆F
– 各都市の、開設施設への割当φ: C→I
– 開設コストと接続コストの総和が最小になるよう
にする
問題の定式化
minimize
subject to
c x   f y
 x  1 ( j  C)
ij ij
iF , jC
jF
iF
i i
ij
yi  xij  0 (i  F , j  C)
xij {0,1} (i  F , j  C)
yi {0,1} (i  F )
xij : 都市jが施設iに接続されれば
1, そうでなければ
0
yi : 施設iが開設されれば
1, そうでなければ
0
cij : 都市jの、施設
iへの接続コスト
LP緩和と双対問題
主問題
minimize
subject to
c x   f y
 x  1 ( j  C)
ij ij
iF , jC
iF
iF
i i
ij
yi  xij  0 (i  F , j  C)
xij  0
(i  F , j  C)
yi  0
(i  F )
双対問題
maximize

jC
j
subject to  j  ij  cij (i  F , j  C)
 ij  fi (i  F )
jC
j 0
ij  0
( j  C)
(i  F , j  C)
 j , ij ：
双対変数
fi ：
施設iの開設コスト
相補条件
•
主相補条件
i. 任意の i  F , j  C に対して、 xij
 0  j  ij  cij
緩和
開設コストを支払う都市を直接接続の都市、支払わな
い都市を間接接続の都市とする。このとき、
間接接続の都市 j に対して、1 3c ( j ) j   j   ( j ) j  c ( j ) j
ii.
•
任意の i  F に対して、 yi  0 

jC
ij
 fi
双対相補条件
iii. 任意の j  C に対して、 j  0   xij  1
iF
iv. 任意の i  F , j  C に対して、 ij  0  y j  xij
相補条件のイメージ
• 各都市が、施設への接続と施設の開設にコストを払うと考え
る
• 都市 j が支払う全コスト：  j  ij  cij
– 施設 i に対して、辺(i, j)を利用する接続のコスト： cij
– 施設 i の開設に対する j の貢献分： ij
相補条件のイメージ
• 各都市が支払うコストは2種類
– 施設を開設するためのコスト
– 施設に接続するためのコスト
• 都市 j は、接続する施設に対してのみ、開設費用を支払う
• 施設 i の開設コストは、この施設に接続されている都市に
よって完全に支払われている
アルゴリズム24.2―フェーズ1
双対解を求め、仮想的に開設する施設Ft を求める。
• 時間0からスタート
• はじめ、各都市は未接続の状態にあるとする
t=0
0/2
0/3
0/5
0/5
: unconnected
0/9

0/2
0/1
j
0/5
0/8
fi
( j  ij ) cij
0/7
0/4
facility
ij
0/6
city
• 各都市ｊに対して、双対変数αj の値を単位時間あたり1
ずつ増加させる
アルゴリズム24.2―フェーズ1
• ある辺(i, j)でαj =cij となったとする。
このとき、辺(i, j)はタイトになったと宣言する。
これ以降、βij も一様に増加される。
• βij ＞0である辺は特別な辺と宣言される。
t=1
↓
t=2
0/3
0/5
↓
1/5
1/2 →2/2
1/9 →2/9
1/5 →2/5
: unconnected
1/2 →2/2
1/1
0/4
facility
1/8 →2/8
1/5
↓
2/5
1/7
→2/7
1/6 →2/6
: tight
: special
city
アルゴリズム24.2―フェーズ1
• 施設 i は、  j ij  fiのとき完済されたといい、
この施設を仮想的開設と宣言する。
• 仮想的開設の施設にタイトな辺でつながっている未接続の
都市は、既接続と宣言される。
• 施設 i は、これらの都市のそれぞれに対して接続立証人と
2/2
宣言する。
3/3
t=5
↓
t=6
終了
5/5
4/5
↓
5/5
: unconnected
5/9 →6/9
2/2
: connected
1/1
3/4
facility
: temporarily
open
5/5
5/8
5/7 →6/7
5/6
: tight
city
: special
• すべての都市が既接続になったら、フェーズ1は終了。
アルゴリズム24.2―フェーズ2
実際に開設する施設の集合Iと、
各都市をIに割り当てる関数φを求める
• 仮想的開設の施設の集合をFt とする。
• 特別な辺全体からなるGの部分グラフをTとする。
• uとvとを結ぶ長さ高々2のパスがTに存在するとき、その
ような辺(u, v)からなるグラフをT2とする。
• Ft で誘導されるT2の部分グラフをHとする。
G
T
Ft
facility
city
T2
city
facility
H
: temporarily
open
: tight
: special
facility
city
facility
アルゴリズム24.2―フェーズ2
I
• Hの極大独立集合Iを求める。
• I に含まれる施設を全て開設と宣言する。
open!
• 各都市 j に対して、Fj  {i  Ft | (i, j)は特別な辺}
と定義する。
Ft
Fp  {a, b, c}
Fq  {b}
Fr  
a
p
: connected
: open
b
q
: temporarily
open
: tight
c
r
facility
city
: special
アルゴリズム24.2―フェーズ2
•
•
各都市をI に割り当てる関数φを求める。
都市j について、3通りの場合を考える。
1. 施設 i Fj が開設されている場合
2. F j のどの施設も開設されていない場合
j の接続立証人i’ について
1. i  I のとき
a
2. i  I のとき
b
c
facility
Fp  {a, b, c}
p : case1
Fq  {b}
q : case2-2
Fr  
r : case2-1
city
φ:C→Iの求め方
1. 施設 i Fj が開設されている場合
–  ( j)  i とする
– 都市j は施設iに直接接続と宣言される
2-1. F j のどの施設も開設されていない場合で、
j の接続立証人i’が i  I を満たす場合
–  ( j)  iとする
rの接続立証人
– 都市j は施設i に
直接接続と宣言される a
 ( p)  a
p : case1
q : case2-2
b
c
facility
 (r )  a
r : case2-1
city
φ:C→Iの求め方
Fj
のどの施設も開設されていない場合で、
j の接続立証人i’が i  I を満たす場合
– i’ は仮想的開設の施設
– I はグラフHの極大独立集合より、 i  I となるi’の隣接点
i が存在する
– そこで、  ( j)  i とし、都市j は施設i に間接接続と宣言さ
れる
2-2.
a
p : case1
 (q)  a
qの接続立証人
H
a
b
iI
b
q : case2-2
i  I
c
r : case2-1
facility
city
定理24.7
アルゴリズムで求められた主問題の解と双対問題
の解は、以下の不等式を満たす。
c x
ij ij
iF , jC
 3 fi yi  3 j
iF
jC
補題24.4
f
e






双対変数 j について、 j
j
j とする。
f
–  j ：都市 j が支払う、施設開設コスト
e

– j ：都市 j が支払う、開設施設への接続コスト
このとき i  I とすれば、以下が成立する。



j: ( j ) i
f
j
 fi
補題24.4の証明
• 都市 j が支払う施設開設コストは、 j が
f
– 直接接続の都市であるとき：  j  ij
– 間接接続の都市であるとき：  jf  0
• 一方、開設する施設 i について
– i は仮想的開設の施設でもある
– 施設 i は j ij  fi を満たすとき仮想的開設となる
– したがって、フェーズ1の終了時には  ij  fi を満たし
j:(i , j )は特別な辺
ている
• 施設 i の開設に貢献している都市は、 i に直接接続している
都市のみ
f

• したがって、  j 
 ij  fi

系24.5
j: ( j )i
j: jはiに直接接続
 f  
iI
i
jC
f
j
補題24.6
間接接続の都市j に対して、 i   ( j) とすれば、
cij  3 ej が成り立つ。
[証明]
• 施設 i’ を都市 j の接続立証人とする。
• j は i に間接接続されているので、(i, i’)はHの辺
⇒(i, j’)と(i’, j’)が特別な辺となるような都市 j’ が存在する
• 辺(i’, j)はタイトなので、 j  cij
• 辺(i’, j’)と(i, j’)もタイトなので
i
j’
 j  cij かつ  j  cij
間接接続
i’
j
facility
city
補題24.6の証明
• i と i’ がフェーズ1で仮想的開設と宣言された時刻を、それぞ
れt1, t2とする。
• 2つの辺(i’, j’), (i, j’)はともに特別な辺なので、 i あるいは i’
が仮想的開設と宣言される前にタイトになっている。
• i , i’ のどちらかが仮想的開設と宣言されれば、都市 j’ は既
接続になり、時刻min(t1, t2)以降  jが増加することはない。
つまり、  j  min(t1, t2 )
i
j’
• また、 i’ が仮想的開設と宣言された
時に j は既接続となるので、 j  t2
• よって、 j   j
i’
• これと  j  cij ,  j  cij ,  j  cij facility
j
と三角不等式より、
city
cij  cij  c jj  cij  cij  cij  3 ej
定理24.7の証明
• 都市 j が支払うコストの総和を j とし、
–  jf ：都市 j が支払う施設開設コスト
e
–  j ：都市 j が支払う、開設施設への接続コスト
とする。
e
e
c



3

• 直接接続の都市 j に対して、φ( j )= i のとき、 ij
j
j
が成立する
• 補題24.6より、間接接続の都市 j に対して、 φ( j )= i のとき、
cij  3 ej が成立する
これらより、  cij xij  3 ej (1)
iF , jC
jC
ここで系24.5より、  fi   jf (2)
iI
jC
(2)式を3倍して(1)式に加えると、 cij xij  3 fi yi  3 j
iF , jC
iF
jC
アルゴリズム24.2の計算時間
〔アルゴリズムの実装方法〕
• 辺がタイトになる順番と時刻を求めるため、辺をコストの増加
順にソートする。  O(m log m)
• 各施設 i に対して、開設費用の完済予想時刻 ti を管理する。
• ti は子を2つもつヒープで管理され、イベントが起こるたびに
ヒープが更新される。  O(log n f )
• ヒープ更新の対象となるイベントは2種類。
– 辺(i, j)がタイトになるとき。
– 都市 j が既接続となるとき。
〔計算時間〕
グラフGの辺数をm, 施設の数をnf とすると、 O(m log m)
Part2. k-メディアン
メトリック k-メディアン
• 入力
– 2部グラフG
• 施設の集合F
• 都市の集合C
– 開設できる施設の最大数k（正定数）
– 都市j の、施設i への接続コストcij
• 出力
– 開設する施設I⊆F（施設の数はk個以下）
– 各都市の、開設施設への割当φ: C→I
– 接続コストの総和が最小になるようにする
容量制限なしメトリック施設配置
open!
接続コスト 5
開設コスト 10
25
5
10
30
15
25
5
open!
15
施設の集合F
10
15
都市の集合C
cost : (10+15)+(5+10+15)=55
問題の定式化
minimize
c x
subject to
x 1
ij ij
iF , jC
jF
ij
( j  C)
yi  xij  0 (i  F , j  C)
  yi  k
iF
xij {0,1} (i  F , j  C)
yi {0,1} (i  F )
xij : 都市jが施設iに接続されれば
1, そうでなければ
0
yi : 施設iが開設されれば
1, そうでなければ
0
cij : 都市jの、施設
iへの接続コスト
k : 開設する施設数の上限
LP緩和と双対問題
主問題
minimize
subject to
c x
x 1
双対問題
maximize
ij ij
iF , jC

jC
j
 zk
subject to  j  ij  cij (i  F , j  C)
iF
ij  z (i  F )

yi  xij  0 (i  F , j  C)
jC
 yi  k
j 0
( j  C)

iF
ij  0
(i  F , j  C)
xij  0
(i  F , j  C)
z0
y 0
(i  F )
ij
( j  C)
i
 j , ij ：
双対変数
z
：
定数(コスト
)
k-メディアン問題の解法
• 実行可能小数解を求める
↓
• 乱数使用ラウンディングにより、整数解を求める
↓
• 脱ランダム化を行う
k-メディアン問題を解くアイデア
• 定理24.7より、施設配置問題に対するアルゴリズムで求めら
れた、主問題の解と双対問題の解は
c x
ij ij
iF , jC
 3 fi yi  3 j
iF
jC
を満たす。
• ここで施設の開設コストを全てzとし、かつちょうどk個の施設
を開設したとすると
c x
ij ij
iF , jC
 3zk  3 j
jC
解 ( x, y)はk-メディアン問題に対する最適解に対して3倍以内
のコストになることがわかる。
⇒この式は、開設する施設の数がk個でないと成立しない
ちょうどk個の施設を開設するには?
• k2>k個の施設が開設されるzの値z2と、
k1<k個の施設が開設されるzの値z1を求める。
• z1, z2を求める方法⇒区間[0, ncmax]で2分探索を行う
– z=0ならば、施設の開設コストがかからない
⇒全ての施設を開設すればよい
– z≧ncmax(cmaxは辺の長さの最大値)ならば、ひとつの施設の開設コス
トは、全ての施設が支払う接続コストの総和を超えてしまう
⇒開設される施設は1個のみ
• cminを非零の辺の長さの最小値としたとき、z1  z2  cmin (12nc2 )
となるようにする（ただし、ncは都市の数）
実行可能小数解を求める方法
•
s
y
iF i  k1として、アルゴリズム24.2を実行する。
s
s
s
s
(
α
,
β
) とする。
(
x
,
y
)
得られた主問題と双対問題の解を
,
• 同様に iF yil  k2 として、アルゴリズム24.2を実行する。
l
l
l
l
得られた主問題と双対問題の解を ( x , y ) , (α , β ) とする。
s
s
• ( x, y) を、2つの解( x , y ) , ( xl , yl ) の凸結合とする。
( x, y)  a( x s , y s )  b( xl , yl )
• ただし、
k2  k
a
,
k2  k1
k  k1
b
k2  k1
得られた解は実行可能解?
• ( x, y) は施設配置問題に対して、ちょうどk個の施設
を開設するような実行可能（小数）解
• k-メディアン問題に対しても実行可能（小数）解に
なっている
• アルゴリズム24.2において、各都市に接続している
施設の数は、高々1個
⇒この手法によって得られる解では、各都市に接
続している施設の数は高々2個
補題25.2
( x, y)のコストは、k-メディアン問題の最適小数解の
コストの(3+1/nc)倍以内である。
[証明]
• 定理24.7より、アルゴリズムで求められた主問題の解と双対
問題の解は cij xij  3( j   fi yi ) を満たす。
iF , jC
jC
iF
• k-メディアン問題では
– 各施設の開設コストは、k1個の施設が開設されるときz1、
k2個の施設が開設されるときz2
s
l
– iF yi  k1, iF yi  k2
としているので、以下の式が成り立つ。


s
s
c
x

3
(

 ij ij  j  z1k1)
iF , jC
jC
l
l
c
x

3
(

 ij ij  j  z2k2 )
iF , jC
jC
補題25.2の証明
• 2番目の不等式のz2を、z1で置き換える。
z1  z2  cmin (12nc2 ) , iF , jC cij xijl  cmin を用いて2番目
の不等式を変形すると、


1 
l
 j  z1k2 
c x   3  nc  

 jC

l
ij ij
iF , jC
が得られる。
s
s
c
x

3
(


• この不等式をb倍して、1番目の不等式  ij ij
j  z1k1 )
iF , jC
jC
をa倍したものに加えると、


1 
cij xij   3    j  z1k 

iF , jC
 nc  jC

s
l
α

a
α

b
α
が得られる。（ただし
）
補題25.2の証明
• z1＞z2であるので、 (αl , β l ) は、施設開設のコストをz1にした
施設配置問題の双対問題でも実行可能解になっている。
s
l
s
l
α

a
α

b
α
,
β

a
β

b
β
• したがって
としたとき、
(α, β, z1) はk-メディアン問題の双対問題の実行可能解に
なっている。
したがって、補題が成り立つ。
乱数使用ラウンディング
l
l
s
s
• A, Bを2つの解 ( x , y ), ( x , y ) で開設される施設の集合と
する。
• このとき、 A  k1, B  k2 (k1  k  k2 )
[準備]
• 集合Bの中から、k1個の施設を含む部分集合B’⊂Bを選ぶ。
– Aの各施設に対して、Bの施設の中から最も近い施設を探してくる。
– 得られた施設の集合をB’とする。
– |B’|＜k1ならば、|B’|=k1となるまで
B-B’から勝手に選んでくる。
B’
：開設される施設
：開設されない施設
：集合B’の要素
facility A
city
facility B
乱数使用ラウンディング
• 開設する施設k個を求め、これらの施設の集合をIとする。
– 確率aでAの施設全部を開設し、確率b=1-aでB’の施設全部を開設す
る。
– さらに、B-B’からランダムにk-k1個の施設を選んで開設する。
• 各都市をIに割り当てる関数φ:C→Iを定義する。
– 都市 j について考える。
– 2つの解において、j は i1  A と i2  B に接続されているとする。
– i  B の場合と
2
i2  B  B の場合に分けて考える。
case1
B’
case2
B-B’
facility A
city
facility B
乱数使用ラウンディング
• 各都市をIに割り当てる関数φ:C→Iを定義する。
• case1: i2  Bの場合
– i1とi2のいずれかは必ず開設される。
– 都市 j は開設されたほうの施設に接続される。
• case2: i2  B  B の場合
– i3  B をi1に最も近いBの施設とする。
– i2が開設される場合は、i2に接続される。
– i2が開設されずにi1が開設された
場合は、i1に接続される。
i1
– i1もi2も開設されない場合は、
i3に接続される。
i3
B’
i2
B-B’
facility A
city
facility B
補題25.3
cost( j)  aci1 j  bci2 j とする。
整数解における、都市 j の接続コストの期待値
E[c ( j ) j ] は、 (1, max(a, b))cost( j)以下である。
さらに、 E[c ( j ) j ]は効率的に計算できる。
[証明]
• i2  Bの場合は確率aでi1が、確率bでi2が開設され
るので、
E[c ( j ) j ]  aci1 j  bci2 j  cost( j)
• 次に i2  B の場合を考える。
補題25.3の証明
• i2  B  B のとき、i2が開設される確率を求める。
– i2は、B-B’からランダムに選ばれるk-k1個の施設の中に
含まれていれば、開設される。その確率は、
k  k1
k  k1

b
B  B k2  k1
– i2が開設されていなくて、 i1が開設される確率は
(1  b)a  a2
– i2とi1のどちらも開設されていない確率は
(1  b)(1  a)  ab
したがって、
E[c ( j ) j ]  bci2 j  a ci1 j  abci3 j
2
補題25.3の証明
• i3はi1に最も近い施設であり、接続コストは三角不等式を満た
している。したがって、以下の不等式が成り立つ。
ci1i3  ci1i2  ci1 j  ci2 j
ci3 j  ci1 j  ci1i3  2ci1 j  ci2 j
• この式を E[c ( j ) j ]  bci j  a2ci j  abci j に代入して、
2
1
3
E[c ( j ) j ]  bci2 j  a 2ci1 j  ab(2ci1 j  ci2 j )
 (aci1 j  bci2 j )  ab(ci1 j  ci2 j )
 (aci1 j  bci2 j )(1  max(a, b))
i1
いずれの場合も、
E[c ( j ) j ]は容易に計算できる。
i3
j
facility A
i2
city
B’
B-B’
facility B
補題25.4
k
k
• ( x , y ) を、乱数使用のラウンディング手続きを用い
て得られたk-メディアン問題の整数解とする。
• このとき



k
E  cij xij   (1  max(a, b))  cij xij 
iF , jC 
 iF , jC 
であり、さらに得られる解のコストの期待値は効率
的に計算できる。
脱ランダム化
• 条件付き期待値法を用いて脱ランダム化を行う。
• まず、開設するk1個の施設(AまたはB’)を決定する。
– Aを選び、B-B’からk-k1個の施設をランダムに選んだとき
の期待値を計算する。―①
– B’を選び、①と同様にして期待値を計算する。―②
– ①と②の期待値のうち、小さいほうを選び、対応する施設
（AまたはB’）を開設する。
①：
A
+
B-B’
②：
B’
+
B-B’
B’
B-B’
facility A
city
facility B
脱ランダム化
• 条件付き期待値法を用いて脱ランダム化を行う。
• 次に、B-B’の中からk-k1個の施設を決定する。
– D⊂B-B’を、|D|≦k-k1であるような施設の集合とする。
– Dの全ての施設と、B-(B’∪D)からk-k1-|D|個の施設をラン
ダムに選んで開設したとする。
– このとき解のコストの期待値をE[D, B-(B’∪D)]とする。
B’
D
B-B’
facility A
city
facility B
この中から
k-k1-|D|個選ぶ
脱ランダム化
• B-(B’∪D)の各施設が開設される確率は等しい。よって、
E[ D, B  ( B  D)] 
1
E[ D {i}, B  ( B  D {i})]

B  (B  D) iB( BD)
が成り立つ。
• この式は、
E[D {i}, B  (B  D {i})]  E[D, B  (B  D)]
を満たす施設 i が存在することを意味している。
• したがって、このような i を選んで、DをD∪{ i }に置き換えて
いけば脱ランダム化できる。
近似保証と計算時間
• 定理25.5
アルゴリズムはk-メディアン問題に対して近似率6を達成
し、その計算時間はO(mlogm(L+logn))である。
• 近似保証
– k1  k 1 かつ k2  nc とすれば、a  11 nc
– k1  1 かつ k2  k 1 とすれば、b  11 k
これらより、1  max(a, b)  2 1 nc
(ncは都市の総数)
– 補題25.2より、アルゴリズムで得られる実行可能小数解
のコストは、最適小数解のコストの 1 max(a, b)倍以内
– 補題25.4より、アルゴリズムで得られる整数解のコストは
実行可能小数解のコストの 3 1 nc 倍以内
近似保証の上界は (2 1 nc )(3 1 nc )  6
計算時間
• k2>k個の施設が開設されるzの値と、k1<k個の施設が開設さ
れるzの値を、2分探索により求める。
– 探索区間は[0, ncmax]、区間の長さがcmin/(12nc2)となるま
で行う
– その回数は O(log2 (n3cmax cmin))  O(L  log n) 回
(L  log(cmax cmin))
– 1回の2分探索にかかる時間は O(m log m)
• 乱数使用ラウンディングの計算時間は O(n)
• 脱ランダム化の計算時間はO(m)
これらより、アルゴリズム全体の計算時間は
O(m log m(L  log n))
(mは辺の総数)
整数性ギャップ
• n+1個の点からなるスターグラフ
• 辺のコストは全て1，k=n-1とする
• 最適整数解
– Cの要素となる点の中からn-1個の点を開設
– コストは2
• 小数解
– 中心点を1/(n-1)，残りの点を(n-2)/(n-1)開設
(n-2)/(n-1)
– コストはn/(n-1)
• 整数解と小数解との比は
2(n 1)
n
(n-2)/(n-1)
1
1
: city
(n-2)/(n-1)
1
(n-2)/(n-1)
1
: facility
(n-2)/(n-1)
1/(n-1)
0
0
2
2
l クラスタリング問題
演習問題25.6
• 入力
d
– R のn個の点の集合 S  {v1,, vn }
– 正定数k
• 出力：最小コストのk-クラスタリング
d
– k個のセンター： f1, fk  R
– 各点 vi から最も近いセンターまでの距離を di とする
2
d
– di について、 i の総和が最小となるようなセンターを求
める
f1
f2
f3
f4
k-クラスタリングとk-メディアン
……
……
cost(square of Euclidean distance)
• k個の施設を開設
⇒k個のクラスタへの分割
• 各都市の、施設への割り当て
⇒各点の、クラスタへの割り当て
facility
(centroid of each
subset of points)
city
(n given points)
このままの形だと施設の数が多すぎるので、
施設の数を減らす
↓
施設の集合＝入力されたn個の点の集合S
k-クラスタリングとk-メディアン
cost(square of Euclidean distance)
• センターを入力された点集合
Sに限定
• 得られた2部グラフについて、
k-メディアン問題に対する近似
アルゴリズムを適用
facility
(n given points)
city
(n given points)
この問題に対する最適解のコストは、
もとの問題に対する最適解のコストの2倍以内になる
l
2
2 クラスタリング問題の解のコスト
• 点v1,…,vtが一つのクラスタを形成している
とし、
v3
このクラスタのセンターをf1とする。
• v1,…,vtのcentroidを c  (v1   vt ) t
とすると、
t
t
 vi  f1   vi  c  t f1  c
2
i 1
2
c v
1
v2
f1
2
i 1
が成り立つ。（ u  v は、uとvの間のユークリッド距離の2乗）
• いま、点cから最も近い点をv1とすると、
t
 v v
i 1
i
1
2
t
t
  vi  c  t v1  c  2 vi  c
i 1
2
2
2
i 1
が成り立つ。よって解のコストは最適解の2倍以内になる。
アルゴリズムの近似保証
• この章で扱った問題はメトリックk-メディアン
⇒接続コストは三角不等式を満たす
• 今考えている問題は、辺のコストが距離の2乗
⇒三角不等式が成立するとは限らない
• この場合、アルゴリズム24.2（施設配置問題に対す
るアルゴリズム）の近似保証は9になる
• 同様に、乱数使用ラウンディングによって得られた
解のコストも、小数解の6倍以内となる
• したがって、アルゴリズム全体の近似保証は
2×9×6 = 108

Download Report