STA Chapter3 part2 - nsasakiの勉強メモ

(α,ε)近似の定義

$y ^{'}$ がyの(α,ε)近似とはα>1,ε<1に関して
$y \le y^{'} \le \alpha y + \epsilon n$
をみたすこと。

考える問題の前提(この部分がDistributed computingの使用)

入力

コミュニケーションネットワーク

定義

各頂点はプロセッサー
各エッジはコミュニケーションのライン
グラフは同期しており各ラウンドで各プロセッサは隣のプロセッサと会話
次数d以下でグラフはsparse 平均次数 $\bar{d} = \Omega \left( d \right)$
すべてのプロセッサはdの値を知っている
kラウンド後に各プロセッサは自分の知りえた範囲内でvertex coverになるか否かを決定できる

Simple Case

vertex coverをkラウンドで解く決定型分散アルゴリズム $\mathcal{D}$ について準線形「Oracle Reduction Algorithm」*1を考える。

頂点vがvertex coverか否かを答える。
vはkラウンド後にvからkステップいないの頂点と辺を知りうる。このサブグラフをvの「k neighborhood」と呼ぶ。
※0ラウンド目は自分から一つはなれた頂点とその間の辺を知っている

計算量
$O \left( \frac{d^{k+1}}{\epsilon^{2}} \right)$
vertex coverの数 $\mathcal{C}$ に対して、ここで得られるcは
$| \mathcal{C} | \le c \le | \mathcal{C} | + \epsilon n$
をみたす

Oracle Reduction Algorithm (with oracle acess to $\mathcal{D}$ )

Sの生成

$s = \frac{8}{\epsilon^{2}}$ の[n]でi.i.d*2のノード抽出

$G_{k} \left( v \right)$ をvのk neighborhoodとする。

クエリ $\mathcal{D} \left( G_{k} \left( v \right) \right)$
$X_{v} = \begin{cases} 1 \; \; \mathrm{if} \: \mathcal{D} \left( G_{k} \left( v \right) \right) \: \mathrm{adds} \: v \: \mathrm{to} \; \mathrm{cover} \\ 0 \; \; \mathrm{else} \end{cases}$

出力

$c = n \cdot \left( \frac{1}{s} \sum_{v \in S}X_{v} \right) + \frac{\epsilon}{2}$

Correctness

$X_{v} = 1, v \in C$ のときにのみ $X_{v}$ のcoverは一致する。
$E \left[ X_{n} \right] = \frac{1}{n} \sum_{v \in V} X_{v} ,| \mathcal{C} | = n E \left[ X_{v} \right]$
とおくことにより、前回のChernoff boundから
$Pr \left[ | \frac{1}{s} \sum_{v \in S}X_{v} - E \left[ X_{v} \right] | \ge \frac{\epsilon}{2} \right] \le \frac{1}{3}$
となる。

Query Complexity

$O \left( \frac{d^{k+1}}{\epsilon^{2}} \right)$ の中の
$\frac{1}{\epsilon^{2}}$ はs中のvに対する $G_{k} \left( v \right)$ の回数。
$d^{k+1}$ は $G_{k} \left( v \right)$ における上界

Remark

cに(εn/2)を加えたのは、 $| \mathcal{C} | \le c \le | \mathcal{C} | + \epsilon n$ とするため
errorの範囲を減らすために何回もしましょう

General Case

Simple Caseで用いたような決定性の多項式時間の問題は存在しない。
乱択アルゴリズムを用いたら同様いできますと言う話。

A Distributed Approximation Algorithm for Vertex Cover

$C \leftarrow \mathbb{0}$
i = 1 からlog dまで

次数 $\frac{d}{2^{i}$ 以上の各vをCに加える
Vから先ほど加えたvとそれに隣接するエッジを除く
残った頂点の次元を更新

を出力

$VC_{G}$ を最適解とすると、
$VC_{G} \le | C | \le \left( 2 \log{d} + 1 \right) VC_{G}$
となる。

[証明]

左辺

捜査終了後にエッジが残っており、各エッジに対する頂点がいずれかは除去されているためCはvertex cover

右辺

θを最小vertex coverに含まれる頂点の集合とする
$\bar{\theta}$ をVの中でθでないものとする。
$Y_{i}$ を各iの反復作業で残っている頂点とする。現段階での次数は $\frac{d}{2^{i-1}} \sim \frac{d}{2^{i}}$
$X_{i} := Y_{i} \cap \bar{\theta}$ とする。
$X_{i}$ のエッジの向かう先の頂点は必ず集合θ(θはminimum vertex coverのため $X_{i}$ が $\bar{\theta}$ ということはもう片方の頂点はθ)
エッジについて
Fを $\theta$ と $\bar{\theta}$ とをつなぐエッジ
$F^{'}$ を $\theta$ と $X_{i}$ とをつなぐエッジとすると
$\frac{d}{2^{i}} \le | F^{'} | \le | F | \le |\theta| \frac{d}{2^{i-1}}$
となる。ゆえに、
$| X_{i} | \frac{d}{2^{i}} \le 2 | \theta | \le 2 VC_{G}$
各iに関して成立するため
$| c | \le \left( 2 \log{d} + 1 \right) VC_{G}$
となる。