chap3.4-3.5

3.4 Packing
吉永直生
パッキング
• CをRd上の測定可能な部分集合、B(x)を
キューブ[0, x]dと置く。
• パッキングとは、Cのコピーを重ならないよう
にB(x)の内部に詰めること。
• どれだけ詰められるかを示す値として、以下
の値δ(C)を用いる。ただしμ(C)はCの測度。
δ(C) ＝ μ(C) limx→∞f(x)x-d
• これはCがB(x)を占める割合を示す。
定理 3.4.1
• Cを有限で凸であり、原点を中心とした点対
称であるとすると、以下の式が成り立つ。
δ(C) ≧ 2-d-1
• これは仮定を満たすCならば、どんな形でも
ある程度詰められるということを示している。
• 実際にこの条件を満たすアルゴリズムを以下
で示す。
コピーが重なる確率
• P,QをB(x)の1要素(空間上の1点)と置く。
• (C+P)∩(C+Q)≠φとなった時の事を考える。
• これはつまり、点Pと点Qに中心を置いた二つ
のCのコピーが、重なってしまったということ。
• この場合、ある点c1,c2∈Cが存在し、以下の
式が成り立つ。
P-Q ＝ c1-c2 ＝ 2・(c1-c2)/2 ∈ 2C
コピーが重なる確率
• この式は、Cが凸で中
心に対して点対称であ
ることより導かれる。
• 右の図では、c1とc2は
同じ場所で、PQの中点。
(c1は左の図形の点、c2
は右の図形の点と考え
る。)
コピーが重なる確率
• 先の式を書き換えると、P∈Q+2C
• P∈Q+2Cとなる確率は、多くともμ(2C)x-dなの
で、以下の式が成り立つ。
Pr[(C+P)∩(C+Q)≠φ]≦2dx-dμ(C) — (式1)
アルゴリズム
• ランダムにn点P1,...,Pnを取る。
• Cのコピーをn点に配置する。
• 二つのコピーについて重なりがあった場合、
どちらかを削除する。
アルゴリズムの解析
• 点P1,...,Pnに対して、 (C+Pi)∩(C+Pj)≠φであ
るような(i, j)組み合わせの数をXと置く。
• 式1より、Xの期待値は以下の式の通り。
E[X]≦(n2/2)2dx-dμ(C)
• よって上手くn個の点を取ると、重なりを削除
した後残るコピーの数がn-(n2/2)2dx-dμ(C)よ
り大きくなる。
アルゴリズムの解析
• この式はn＝xd2-d/μ(C)で最大値を取り、その
値はxd2-d-1/μ(C)である。
• 端にあるコピーは、B(x)の内部に納まらない
可能性があるが、xが十分大きい場合その個
数は無視できる。
• よって以下の式が成立する
δ(C) ≧ μ(C) limx→∞(xd2-d-1/μ(C))x-d≧2-d-1
3.5 Recoloring
グラフの塗り分け問題
• グラフの頂点を赤または青で塗り、接した頂
点が全て同じ色で塗られてしまう枝が存在し
ないようにする、という問題を考える。
• 一つの枝が三つ以上の頂点を含んでも良い、
超グラフを考え、n-uniform(どの枝もちょうどn
個の頂点を含む)なものを扱う。
• m(n)とは、m(n) ＞ mである全てのmにおい
て、枝の数がmである全てのn-uniform超グ
ラフにおいて塗り分けが成功するような値。
塗り直し
• 塗り分けが成功しなかった時、いくつかの頂
点の色を変えて、単色の枝を無くそうとする
操作を考える。
• 塗り直す頂点の数が少なすぎると単色の枝
が残ってしまい、多すぎると新たに単色の枝
が生まれてしまう。
• 塗り直す頂点の多さをパラメータp∈[0, 1]で表
す。
定理 3.5.1
• ある値p∈[0, 1]が存在してk(1-p)n+k2p＜1が
成り立つ時、以下の式が成立する。
m(n)＞2n-1k
• k(1-p)n+k2pとは、パラメータpの塗り直しが失
敗する確率。
• k(1-p)nは塗り直す頂点の数が少なすぎて失
敗する確率。k2pは多すぎて失敗する確率。
定理 3.5.1
• つまりこの定理は、u-uniformな超グラフにお
いて、枝の数が2n-1kより小さいならば、成功
する確率が正であるような塗り直しの方法が
存在するから、塗り分けが可能である(よって
m(n)の値はそれより大きい)、という論理を用
いている。
• 実際に塗り直しによるアルゴリズムを示して
証明する。
系 3.5.2
m(n)＝Ω(2n(n/ln(n))1/2)
• (証明) まず、1-p＝e-pである。ke-pn+k2pは
p＝ln(n/k)/nで最小値k2/n[1+ln(n/k)]＜1を取
り、十分大きなnに対してk＝c(n/ln(n))1/2（c＜
√2）の時この不等式は満たされる。
アルゴリズム
• 超グラフはm＝2n-1k本の枝を持つとする。
• 全ての頂点vに対して、1/2の確率で表が出る
コインと、pの確率で表が出るコインを投げる。
• 最初のコインで表が出た頂点を赤で塗り、裏
が出た頂点を青で塗る。全ての頂点を塗り終
わった後、単色の枝に含まれる頂点を、「危
険な」頂点と呼ぶ。
アルゴリズム
• 頂点をランダムに並べて順番に見ていき、そ
の頂点がまだ危険であれば、その頂点の二
番目のコインをチェックする。二番目のコイン
が表ならば、その頂点の色を変える。
• 頂点がまだ危険であるとは、最初の塗り分け
でその頂点が危険であり、かつ塗り直しでも
まだ単色の枝に含まれたまま、ということ。
• 危険な頂点が危険でなくなることはあるが、
逆は無い事に注意。
アルゴリズムの解析
• このアルゴリズムが失敗するのは、塗り直し
前に単色だった枝が一度も塗り直されず単色
のまま残るか、単色で無かった枝が単色に
なってしまうかである。
• ある枝eについて前者の事象をAe、後者の事
象をCeと呼ぶ。
• このアルゴリズムにおいては、ある頂点が二
回塗り直されることは無い事に注意。
単色のまま残る確率
• 最初の塗り分けである枝が単色になってしま
う確率は、2・2-n
• 塗り直しでそれが単色のまま残る、つまり一
度も塗り直しされない確率は、(1-p)n
• よって以下の式が成り立つ
ΣPr[Ae] ＝ 2n-1k・ 2・2-n ・(1-p)n
＝ k(1-p)n
新たに単色ができてしまう確率
• ある枝e, fに対して、eがfを「非難する」とは、
以下の条件を満たす時の事を言う
• eとfは、頂点vのみ共有している。
• 最初の塗り分けにおいてfは青(赤)単色で、塗
り直し後においてeは赤(青)単色。(eは最初
赤(青)単色では無かった事に注意)
• vはeにおいて最後に色が変わった頂点。
• vの色が変わった時、fはまだ青(赤)単色。
新たに単色ができてしまう確率
• これは、 fを単色で無くす為の塗り直しで、e
が単色になってしまったという事を表す。
• 二番目の条件は、このような事が起こり得る
ために必要な条件。三番目はeが確実に単色
になるために必要。四番目はfの為に、という
事を満たす為の条件。
新たに単色ができてしまう確率
• 一番目は他の条件より成り立つ。何故なら他
に共有する頂点v’があったとすると、この頂
点は二番目の条件より塗り直しで色が変わっ
たはずである。
• また三番目の条件よりv’はvより前に色が変
わったはずだが、これは四番目の条件と矛盾
する。
新たに単色ができてしまう確率
• このような事象をBefと置くと、
ΣPr[Ce]≦ΣPr[Bef]が成り立つ。
• ここで、塗り直しでの頂点の並べ替えσについ
て、枝eにおいてvより前にある頂点の数を i
＝i(σ)、枝fにおいてvより前にある頂点の数を
j=j(σ)と置くと、以下の式が成り立つ
Pr[Bef|σ]≦2(p/2)2-n+1(1-p)j2-n+1+i((1+p)/2)i
新たに単色ができてしまう確率
• Pr[Bef|σ]≦2(p/2)2-n+1(1-p)j2-n+1+i((1+p)/2)i
• 最初の2は、色の組み合わせ。
• 第二項は、vが最初青で塗り直しで赤になる
確率。
• 第三項は、fにおいてその他の頂点が最初全
て青である確率。
• 第四項はfにおいてvより前にある頂点が全て
塗り直されない確率。
新たに単色ができてしまう確率
• Pr[Bef|σ]≦2(p/2)2-n+1(1-p)j2-n+1+i((1+p)/2)i
• 第五項はeにおいてvより後にある頂点が最
初全て青であった確率。
• 第六項はeにおいてvより前にある頂点が最
初赤であったか、もしくは最初青で塗り直しに
よって赤になった確率。
• またこの式を書き直すと、下のようになる。
Pr[Bef|σ]≦2-2n+2p(1-p)j(1+p)i
新たに単色ができてしまう確率
• 全てのσについて考えると、以下の式。
• Pr[Bef]≦2-2n+2pE[(1-p)j(1+p)i]
• 後述する定理3.5.3よりE[(1-p)j(1+p)i]≦1な
ので、全てのe,fの組み合わせについて考え
ると、枝の数2n-1kより下の式が導かれる。
ΣPr[Bef]≦Σ(2-2n+2p)
＝ (2n-1k)2/2(2-2n+2)p
＝ k2p/2
アルゴリズムが失敗する確率
• 以上の議論より、アルゴリズムが失敗する確
率Fは以下の式を満たす
F≦ k(1-p)n+k2p
• よってあるnとkについて、右式が1より小さく
なるようなpが存在する場合、そのようなpに
おけるアルゴリズムは成功する場合がある。
• 以上より、定理は証明された。
定理 3.5.3
•
•
•
•
•
E[(1-p)j(1+p)i]≦1
(証明)v以外の、枝eの要素(頂点)とfの要素を
適当に1:1で対応させ、掛け合わせる。
掛け合わせた結果は、1, (1-p)(1+p),
(1-p),(1+p)のいずれかである。
まず1と(1-p)(1+p)はどちらも1以下である。
(1-p)と(1+p)が現れる確率は同じなので、期
待値を取ると1になる。
以上より、 E[(1-p)j(1+p)i]≦1

Download Report