次の2ラウンド分散アルゴリズムは最大マッチングの井戸に近似していますか?

$ G $を無向グラフとする。

私は可能な限り多くの頂点ペアに一致する2ラウンド分散アルゴリズムを探しています。

頂点$ v $に対する以下のプロトコルを考えてみましょう。

  1. 公正なコインを使用して、 { mathit {active}、 mathit {passive} } $の
    “ステータス” $ s_v を選択します。

2.a。 $ s_v = mathit {active}
$がランダムな隣人に要求を送った場合。

2.b. $ s_v = mathit {passive}
$で少なくとも1つのリクエストを受け取った場合は、ランダムに選択された1人のリクエスタに
accept

それぞれの requestaccept
と対になって、結果のマッチングにエッジを追加します。

$ M $を$ G $の最小最大マッチング(すなわち、最小基数との最大マッチング)とし、$ M
‘$を上記のアルゴリズムによって生成されたマッチングとする。

$ mathbb E [| M ‘|]/| M |
$については何が言えるでしょうか?生成されたマッチングは最大マッチングの良い近似であると予想されますか?たとえば、任意のグラフ$ G
$に対して$ mathbb E [| M ‘|]/| M | = Omega(1)$を持つか?

ベストアンサー

いいえ。次のグラフでは、生成されたマッチングの予想サイズは$ O( sqrt n)$ですが、最大マッチングはサイズ$
Theta(n)$です。

このグラフは、$ k $の頂点と頂点($ C $から離れている)とすべての辺$(u、w)$の$ k $ 2 $ $との一致$
M_0 $と$ k $ 2 $ $ in C $と$ w in M_0 $である。

lemma 1. Any maximal matching $M$ has
$Omega(k^2)$ edges

Proof. Every edge in $M_0$ is either in $M$ or is
touched by an edge in $M$ into $C$, but all at most $k$ edges of
$M$ can touch $C$. QED

lemma 2. In your random process, the
expected number of edges chosen in the random matching is
$O(k)$.

Proof. Clearly at most $k$ edges are chosen that are
not in $M_0$ (as there are only $k$ vertices in $C$). For a given
edge $(u,w)$ in $M_0$, the chance that it is chosen is $O(1/k)$,
because, given that, say, $u$ is active and $w$ is passive, the
chance that $u$ picks $w$ is $O(1/k)$, as $w$ has $k$ other edges
(to $C$). QED

(あなたのプロセスについて証明できることの1つは、どのグラフでもエッジの一定部分が生成されたマッチングのエッジに触れるということです、例えば良い頂点を呼び出し、少なくとも半分のエッジを適切な頂点に向ける必要があります(補題6)。良い頂点はプロセス内で一致する確率が一定であるため、エッジの少なくとも半分は、一致する確率が一定の頂点に接触します。

編集:プロセスの$ O( log n)$回後に、それは高い確率で最大マッチングを持つでしょう。)

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です