2011-08-30

STAについて

前期の復習がてらついでに
Tel Aviv UnivのDana RonのLecture Noteも見ています。
Topics in Algorithms – Sublinear Algorithms 0510.7410
http://www.eng.tau.ac.il/~danar/TOP06/index.htm

こちらに載っていることも時間があればちょいちょい書いていこうかと思っています。

Lecture1のモチベーションの部分に自分の考えていなかったことが書いてあったので書きます。
正確な答えをえねばならないときに、その前処理として大きく外れた値を取り除くのにSublinear Time Algorithmsを用いる。
これは確かにそうだなーと思いました。 $sqrt{n}$ とかlogn時間でε-farなものを取り除けられたらこれは効率的なことだと思いました。

Lecture2では与えられたグラフが連結成分であるかどうかをチェックするアルゴリズムが載っていました。

2011-08-26

これから勉強したいこと。

計画

結局、Extremal Combinatoricsを読もうかと思います。

あとは時間があれば
http://www-sop.inria.fr/mascotte/seminaires/AGAPE/notes
のFPTに関するところと
http://www.cs.huji.ac.il/~analyt/
http://www.cs.princeton.edu/courses/archive/fall07/cos597D/Site/coursepage.html
にのってる手法を勉強したいなーと思っています。

優先度的には
Extremal Combinatoricsと前期の復習
80630 - Analytical Methods in Combinatorics and Computer-Science
AGAPE09
COS 597D: How to think like a theorist
ってところです。

ちょっとずつ記事を書こうかと思っています。

2011-07-29

院試前だけど。。　院試後にしたいこと

計画

とりあえず院試の結果次第だとは思うんですが。
研究室の本を色々漁ってて院試後に読めたらなと思うもののリストをさらっと。

アルゴリズムイントロダクション1〜3巻

パラパラ見た感じでは結構基本的なことかも？

数学的基礎とデータ構造 (アルゴリズムイントロダクション)

作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,Thomas H. Cormen,Clifford Stein,Ronald L. Rivest,Charles E. Leiserson,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一
出版社/メーカー: 近代科学社
発売日: 2007/03/01
メディア: 単行本
購入: 13人クリック: 378回
この商品を含むブログ (59件) を見る

アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)

作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,Thomas H. Cormen,Clifford Stein,Ronald L. Rivest,Charles E. Leiserson,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一
出版社/メーカー: 近代科学社
発売日: 2007/03/01
メディア: 単行本
購入: 10人クリック: 169回
この商品を含むブログ (48件) を見る

アルゴリズムイントロダクション第3巻精選トピックス

作者: T.コルメン,R.リベスト,C.ライザーソン,Thomas H. Cormen,Ronald L. Rivest,Charles E. Leiserson,浅野哲夫,梅尾博司,和田幸一,岩野和生,山下雅史
出版社/メーカー: 近代科学社
発売日: 1995/12
メディア: 単行本
購入: 1人クリック: 37回
この商品を含むブログ (28件) を見る

アルゴリズムデザイン

かなり丁寧に書いてあってよさげ。

アルゴリズムデザイン

作者: Jon Kleinberg,Eva Tardos,浅野孝夫,浅野泰仁,小野孝男,平田富夫
出版社/メーカー: 共立出版
発売日: 2008/07/10
メディア: 単行本
購入: 10人クリック: 421回
この商品を含むブログ (51件) を見る

計算理論の基礎

計算量クラスの話とかもうちょい勉強したいなと。
あと、抜けてる知識の補強にもと。。

計算理論の基礎 [原著第2版] 1.オートマトンと言語

作者: Michael Sipser,太田和夫,田中圭介,阿部正幸,植田広樹,藤岡淳,渡辺治
出版社/メーカー: 共立出版
発売日: 2008/05/21
メディア: 単行本
購入: 6人クリック: 68回
この商品を含むブログ (30件) を見る

計算理論の基礎 [原著第2版] 2.計算可能性の理論

作者: Michael Sipser,太田和夫,田中圭介,阿部正幸,植田広樹,藤岡淳,渡辺治
出版社/メーカー: 共立出版
発売日: 2008/05/21
メディア: 単行本
購入: 4人クリック: 23回
この商品を含むブログ (15件) を見る

計算理論の基礎 [原著第2版] 3.複雑さの理論

作者: Michael Sipser,太田和夫,田中圭介,阿部正幸,植田広樹,藤岡淳,渡辺治
出版社/メーカー: 共立出版
発売日: 2008/05/21
メディア: 単行本
購入: 4人クリック: 34回
この商品を含むブログ (17件) を見る

Parameterized Complexity Theory

FPTまわりの知識をつけたいなーと。

Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series)

作者: J. Flum,M. Grohe
出版社/メーカー: Springer
発売日: 2010/02/12
メディア: ペーパーバック
クリック: 1回
この商品を含むブログ (1件) を見る

Extremal Combinatorics

組合せ論の本。Sunflower Lemmaを勉強してたら見つかった。
評判もいいので読んでみたいなーと。

Extremal Combinatorics: With Applications in Computer Science (Texts in Theoretical Computer Science)

作者: Stasys Jukna
出版社/メーカー: Springer
発売日: 2001/06/13
メディア: ハードカバー
クリック: 7回
この商品を含むブログ (2件) を見る

どうせなら洋書にチャレンジするのもありかなと。

2011-05-17

STA Chapter3 part3

Sublinear Time Algorithms

Maximal Matching

Matching

グラフG(V,E)においてマッチングMとは隣り合うエッジの組を求めることどの2つのエッジも頂点を共有しない。

Maximal Matching

Maximal Matchingとは集合Mに対して現状では集合Vの中でで集合Mの補集合からもはや選ぶエッジが存在しないもの

Maximum Matching

Maximum MathcingとはMaximal Matchingの中でエッジの数が最大のもの

Remark

Maximal Matchingの大きさはせいぜいvertex coverの数
次数d以下ならばm/(2d-1)

Greedy Sequential Maximal Matching Algorithm

$M \leftarrow \mathbb{0}$

$\forall e = (u,v) \in E$
u,vともにマッチしていないならeをMに加える

Mを出力
$e = (u,v) \in E \: \mathrm{s.t} \: e \notin M$ 　ならばuかvがマッチしているため。

Implementing Oracle to Simulate Greedy

長ーい鎖状になっていたら一個ずつ調べるためθ(i)ステップ必要になる。
解決策は頂点の番号をランダムに振り当てる。すると、このような鎖は存在しなくなる。

2011-05-17

STA Chapter3 part2

Sublinear Time Algorithms

(α,ε)近似の定義

$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}$
となる。

(2log d + 1, ε)近似で $\frac{d^{\left( \log{d} \right)}}{\epsilon^{2}}$ クエリ必要
なお、最新の結果では(2,ε)近似で $O \left( \frac{d}{\epsilon^{4} \right)$ クエリ必要だとか。

*1:ここでのReductionは還元を意味する

*2:同一分布に従い互いに独立である

2011-05-17

STA Chapter3 part1

Sublinear Time Algorithms

Distributed computing vs. sublinear time

A reduction and a distributed algorithm. Approximating vertex cover and maximal matching in sublinear time.

Introduction

sparse graphs(疎グラフ)EがVに対して比較的少ないグラフ
dense graphs(密グラフ)EがVに対して比較的多いグラフ

Vertex cover(頂点被覆)
入力

グラフG(V,E)

$V^{'} \subset V \forall e = (u.v) \in E,\; \mathrm{either} \; u \in V^{'} \; \mathrm{or} \; v \in V^{'}$
このとき、 $V^{'}$ はvertex cover　すなわち、エッジの両端点のいずれかが含まれることになる。

Approximating Minimum Vertex Cover using Linear Programing

Vertex Cover as Integer Constraints

入力

グラフG(V,E)

条件

$X_{i} \in \left{ 0 , 1 \right} \mathrm{for}\; \mathrm{each} \; \mathrm{i}$
$X_{i} + X_{j} \ge 1\mathrm{for}\; \mathrm{each} \; \left( i , j \right) \in E$

目的

$\sum_{i = 1}^{n} X_{i}$ の最小化(Minimizing Vertex Cover Probelm)

これはNP完全問題なので問題を変換
Integer Programing→Linear Programing

$X_{i} \in \left{ 0 , 1 \right} \rightarrow X_{i} \in \left[ 0 , 1 \right]$

※個人的なメモ:
線形計画問題の復習の必要あり。

The LP Rounding Algorithm

線形問題に緩和した時の解集合 $X^{*}$ をえる。
$X^{*}_{i} \ge \frac{1}{2}$ をみたす $X^{*}_{i} \rightarrow 1 \:\; \mathrm{else} \; X^{*}_{i} \rightarrow 0$ とする。
そのような集合Sを答えとして出す。

SはVertex Cover (元の条件をみたすため)
Sは最適解のせいぜい二倍
- $\hat{X_{i}}$ をLPで解いた時の $X_{i}$ の値とする。
- このとき、IPの最適解をOPTとすると
- $\hat{X_{i}} \le \mathrm{OPT}$ 　問題を拡張したため
- $\sum X_{i} \le 2 \sum \hat{X_{i}} \le 2\mathrm{OPT}$

2011-05-10

STA Chapter2 part3

Sublinear Time Algorithms

Estimating the Weight of the Minimum Spanning Tree

Spanning Tree(以下st)

あるグラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木のこと

問題設定

入力

無向グラフG(V,E)
制限 $\le$ d
各エッジ(i,j)は整数の重み $w_{ij} \in \left[ w \right] \cup \left{ \infty \right}$ をもつ隣接知ると出グラフを与えられウエイト∞のエッジは現れない。

目的

Gのstのウエイト総和が最小となること(以下、この状況のことをMSTと呼ぶ)
$w \left( T \right) = \Sigma_{(i,j) \in T} w_{ij}\; \; T \subseteq E$
$M = \min_{T \text{ spans } G} w \left( T \right)$
とすると、
$\left( 1 - \epsilon \right) M \le \hat{M} \le \left( 1 + \epsilon \right)$
となる $\hat{M}$ をもとめる。

※
$n -1 \le M \le w \left( n -1 \right) \; , \; n = |V|$
となる。
理由はn-1本のエッジを選べばstができるため、かつ各エッジのウエイトは1〜wであるため。

From motivation to characterization

$G^{\left( i \right) } = \left( V , E^{ \left( i \right) } \right)$ はGのサブグラフでウエイトがi以下
$C^{\left( i \right) }$ を $G^{\left( i \right) }$ におけるc.cの数
とする。

A motivation

単純なケース

w = 1のとき
M = n-1
w = 2のとき
$G^{\left( 1 \right) }$ にはウエイト2の $C^{\left( 1 \right) } - 1$ 本のエッジを
$G^{\left( 1 \right) }$ のc.cにつなげばよい。
すなわち、
$2 - \left( C^{\left( 1 \right) } - 1 \right) + 1 \left( n - 1 - \left( C^{\left( 1 \right) } - 1 \right) \right) = n - 2 + C^{\left( 1 \right) }$

w=nへの一般化

$M = n - w + \sum_{i=1}^{w-1} C^{\left( i \right) }$
となる。

証明

GのMSTにおけるウエイトiのエッジの数を $\alpha_{i}$ とする。
ウエイトl以上のエッジの数は $C^{\left( l \right) } -1$ である。
$\therefore \sum_{i = l+1}^{w} \alpha_{i} = C^{\left( l \right) } - 1$
$C^{\left( 0 \right) } = n$
であることより、
$\begin{align} M & = & \sum_{i=1}^{w} i \alpha_{i} \\ & = & \sum_{i=1}^{w}\alpha_{i} + \sum_{i=2}^{w}\alpha_{i} + \cdots + \alpha_{w} \\ & = & \left( n - 1 \right) + \left( C^{\left( 1 \right) } - 1 \right) + \cdots + \left( C^{\left( w-1 \right) } - 1 \right) \\ & = & n - w + \sum_{i=1}^{w-1} C^{\left( i \right) } \end{align}$

Approximation algorithm

MST_approx(G,ε,w)
iからw-1まで
　 $\hat{C}^{ \left( i \right) } = \mathrm{approx \: num \: cc} \left( \hat{G}^{ \left( i \right) } , \frac{\epsilon}{2w} \right)$ *1
最後に、
$\hat{M} = n - w + \sum_{i=1}^{w-1} \hat{C}^{\left( i \right) }$
を出力

各approx_num_ccにかかる計算時間は
$O \left( \frac{d}{ \left( \frac{\epsilon}{2w} \right)^{4} } \right) = O \left( \frac{dw^{4}}{\epsilon}^{4} \right)$
これをw-1回繰り返すため
$O \left( \frac{dw^{5}}{\epsilon^{4}} \right)$
approx_num_ccに関してウエイトi以上のエッジは無視するようにすればよい
$| \hat{C}^{ \left( i \right) } - C^{ \left( i \right) } | \le \frac{n\epsilon}{2w}$
が高確率で成功、各iについてそうであるため
$| \hat{M} - M| = | \sum_{i=1}^{w-1}{\hat{C}^{ \left( i \right) } - \sum_{i=1}^{w-1}C^{ \left( i \right) } | \le \sum_{i=1}^{w-1} |\hat{C}^{ \left( i \right) } - C^{ \left( i \right) } | \le \frac{n \epsilon}{2w} \left( w - 1 \right) \le \frac{n \epsilon}{2w}\left( w \right) = \frac{n \epsilon}{2}$
$n \ge 2$ において、 $\frac{n}{2} \le n -1$ が成立。
また $n - 1 \le M$ である。以上より、
$| M - \hat{M} | \le \frac{n}{2} \epsilon \le M \epsilon$
となる。
現在、 $\Omega \left( \frac{dw}{\epsilon^{2}} \right) , O \left( \frac{dw}{\epsilon^{2} } \log{ \left( \frac{dw}{\epsilon} \right) } \right)$ のアルゴリズムが知られている。

参考資料

作者: Michael Mitzenmacher,Eli Upfal,小柴健史,河内亮周
出版社/メーカー: 共立出版
発売日: 2009/04/24
メディア: 単行本
購入: 2人クリック: 35回
この商品を含むブログ (12件) を見る

*1:はてな記法のtexで_の表示の仕方がわからない:-

アルゴリズムイントロダクション1〜3巻

計算理論の基礎

Parameterized Complexity Theory

Extremal Combinatorics

Maximal Matching

Remark

Greedy Sequential Maximal Matching Algorithm

Implementing Oracle to Simulate Greedy

(α,ε)近似の定義

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

Simple Case

Oracle Reduction Algorithm (with oracle acess to )

Correctness

Query Complexity

Remark

General Case

A Distributed Approximation Algorithm for Vertex Cover

[証明]

左辺

右辺

Distributed computing vs. sublinear time

A reduction and a distributed algorithm. Approximating vertex cover and maximal matching in sublinear time.

Introduction

Approximating Minimum Vertex Cover using Linear Programing

Vertex Cover as Integer Constraints

The LP Rounding Algorithm

Estimating the Weight of the Minimum Spanning Tree

Spanning Tree(以下st)

問題設定

入力

目的

From motivation to characterization

A motivation

単純なケース

w=nへの一般化

証明

Approximation algorithm

参考資料

Connected_component

Spanning_tree

記号Θ(n),Ω(n),O(n),o(n)など、

Chernoff bound の証明

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