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
© Copyright 2024 ExpyDoc