表題論文PDFの輪読会、3.1-3.2章の発表資料です。
Chap.3 Online Bipartite Matching
- オンライン２部マッチングは
Karp et al. (1990)によって提案された> problem statement: U (the boys) and V (the girls)
- ２部グラフ $G(U, V, E)$
- $U$ : known vertexs
- $V$ : オンラインで到着するvertexs
- $E$ : すでに作られたMatchings
- 到着した $v \in V$ はもし隣接する $u \in U$ が存在したらマッチング可能
- 一度作られたマッチは取り消しできない
- マッチングのサイズを最大にするのを目的とする
- 以下、競合比 (competitive ratio) については前回資料を参照のこと
- Online Bipartite Matchingで検索すると、大学の講義資料も多々見つかるlink
Chap.3.1 Adversarial Order
GREEDY
GREEDYアルゴリズム : 到着した $v$ に対してマッチング可能な $u$があればマッチングさせる
Deterministic Algorithm（決定的アルゴリズム）でまず考えてみる。
決定的、とはinputに対してあらかじめ結果が決まっていること。
adversarialな状況では、最悪となるようにマッチングが行われる
GREEDYのアルゴリズムは以下
- 図(a), 図(b)の黒線がedge。図(b)の状態を隣接行列で表すと、図(c)となる。この図で1はエッジを表す。
- 図(a)の状況でadversarialを考えると、v1に対してu2がマッチングされる。そのため、v2に対してマッチングはできない。
- GREEDYではこれ以上edgeが追加できない極大マッチングとなるはず。よって
Theorem 1.2より、competitive ratioは $\frac{1}{2}$- よって、
Theorem 3.1
決定的アルゴリズムでは競合比の上限は 1/2 となり、GREEDYは 1/2.
RANDOM
- RANDOMアルゴリズム : 到着した $v$ に対して、マッチング可能な $u$ 群からランダムにマッチング対象を引き当てる
- 単純な乱択アルゴリズム
- 決定的アルゴリズムと異なり、入力に対してランダムにマッチングを決定する
- この場合、$\frac{1}{2}$よりは悪くならない
- これを使うと、 図3.1の左では競合比は $\frac{3}{4}$ となる
- しかし、上図のように２部クリークがあるようなグラフにおいて、V1群とU2群がマッチングされてしまった場合、 $\frac{1}{2} + o(1)$となる。
- クリーク: 任意のV1群頂点と任意のU2群頂点の間に枝が存在すること
- 基本的には極大マッチングなので、最悪は $\frac{1}{2}$
- 多くの場合は $\frac{1}{2}$ しか達成できない
Theorem 3.2
RANDOMの競合比は 1/2
Chap.3.1.2 RANKING: An Optimal Algorithm
- RANKING
-
correlated randomnessを考慮すれば、RANDOMより改善する、はず -
Karp et al. (1990)により考案 - 競合比 $1 - \frac{1}{e} \simeq 0.63$ となる
- あらかじめ、 $U$ の順列 $\pi$ をランダムに選定
- $v$ に対して $\pi(u)$ の最小値となる $u$ とマッチング
- 全ての $v \in V$ について、同じ $u \in U$を使用することになるので、correlated randomnessが存在する
-
Theorem 3.3
RANKINGはadversarialな状況において競合比の上限は 1 - 1/e となる
- Miss event $(\pi, u^*)$ はn個の Match event $(\pi^{(i)}, u_i)$ と対応付けることが出来る ( $u_i \in U$ )
- よって
\forall t \in [n]:\space n \cdot {\rm Pr[ Miss\, event\, at\, position\,} t] \leq \sum_{s \leq t} {\rm Pr[Match\, event\, at\, position\,} s]
- $x_t\, =\, {\rm Pr[Match\, event\, at\, position\,} t]$ とおくと
\forall t:\, 1 - x_t\, \leq \frac{1}{n} \sum_{s \leq t} x_s
- Factor-Revealing LPを使うと、
ALG = \sum_t x_t \geq (1 - 1/e) n
\\
OPT = n
- よって最悪 $1 - \frac{1}{e}$
Yao's lemma
乱択アルゴリズムでは、1 - 1/eを超えることは出来ない
Chap.3.2 Random Order
- GREEDY with random order は RANKING with adversarial でシミュレート出来る
Theorem 3.4
GREEDY with random orderで、 競合比 1 - 1/eを達成できる。
決定的アルゴリズムでは最高3/4, 乱択アルゴリズムでは5/6となる
- RANKING with random orderでは最悪 1 - 1/e (Karande et al. etc.)
Theorem 3.5
RANKING with random orderにより、競合比0.696を出せる。
もし G(U,V,E)が k個の disjoint perfect matchingであるならば、上限 1 - 1/sqrt(k) となる。
