Sublinear Time Algorithms
前期の復習がてらついでに Tel Aviv UnivのDana RonのLecture Noteも見ています。 Topics in Algorithms – Sublinear Algorithms 0510.7410 http://www.eng.tau.ac.il/~danar/TOP06/index.htmこちらに載っていることも時間があればちょいちょい書いていこう…
Maximal Matching Matching グラフG(V,E)においてマッチングMとは隣り合うエッジの組を求めることどの2つのエッジも頂点を共有しない。 Maximal Matching Maximal Matchingとは集合Mに対して現状では集合Vの中でで集合Mの補集合からもはや選ぶエッジが存在し…
(α,ε)近似の定義 がyの(α,ε)近似とはα>1,ε をみたすこと。 考える問題の前提(この部分がDistributed computingの使用) 入力 コミュニケーションネットワーク 定義 各頂点はプロセッサー 各エッジはコミュニケーションのライン グラフは同期しており各ラウン…
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…
Estimating the Weight of the Minimum Spanning Tree Spanning Tree(以下st) あるグラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木のこと 問題設定 入力 無向グラフG(V,E) 制限d 各エッジ(i,j)は整数の重みをもつ隣接知ると出グラフ…
Estimating the Number of Connected Components Connected Components(連結成分,以下c.cと書く) c.c内の任意の二点間を結ぶパスが存在する。 異なるc.c間にはいかなるパスも存在しない。 問題設定 入力 無向グラフG(V,E) 制限d 目標 c.cの数をcとしたとき、…
Sublinear Time Algorithms Lecture2 やる内容 Chernoff bound Estimating the number of connected components Estimating the weight of the minimum spanning tree Chernoff bound Let be m independent identically distributed random variables such t…
Graph connectivity 入力: G = (V,E), n = |V| , m = |E| , bounded degree d*1 グラフはn×dの隣接行列で与えられる 目的: グラフが連結グラフか? 目的を以下のように変更する Gが連結性にε-closeとは、Gを連結するのに高々εdn本の枝を足せばよいことを言…
Point-set diameter distance matrix -> 距離行列について 配列iと配列jの距離を記述(iとjの距離がDij) >対称行列である(iとjの距離=jとiの距離) 以下を満たす 入力: m×m距離行列d 目的: 直径 を求める。アルゴリズム を適当に取る d(x,y) が最大とな…
これまでの常識: 問題を解くのに入力すべてを見なければ話にならないとされていた。しかし、一部を見るだけで判断できないか?(モチベーションとしては、生体情報やネットワークグラフのようにそれ自体が巨大な量を持つ問題を解きたい) そんなことが出来…