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}