From cca27cd4ba53269697547653abe2843f0a7cb5c4 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 26 Oct 2010 21:44:56 +0200 Subject: [PATCH] Karger-Stein: Opravy drobnych preklepu --- 12-randcut/12-randcut.tex | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-) diff --git a/12-randcut/12-randcut.tex b/12-randcut/12-randcut.tex index c41434b..de98dd4 100644 --- a/12-randcut/12-randcut.tex +++ b/12-randcut/12-randcut.tex @@ -4,7 +4,7 @@ Nahlédnìme alespoò jednou kapitolou do~svìta pravdìpodobnostních algoritmù. Není toti¾ výjimkou, ¾e s~pomocí generátoru náhodných èísel vyøe¹íme nìkteré -grafové problémy daleko snáze a èasto také efektivnìji ne¾ to dovedeme deterministicky. +grafové problémy daleko snáze a èasto také efektivnìji, ne¾ to dovedeme deterministicky. Pravdìpodobnostní pøístup si pøedvedeme na~Kargerovì-Steinovì algoritmu \cite{karger:mincut} pro hledání minimálního øezu v~neohodnoceném neorientovaném grafu. Pøipomeòme, ¾e s~deterministickými algoritmy jsme zatím dosáhli èasové slo¾itosti $\O(n^{5/3}m)$ @@ -13,7 +13,7 @@ pomoc \h{Náhodné kontrakce} Uva¾ujme nejdøíve následující algoritmus, který náhodnì vybírá -hrany a kontrahuje je, dokud poèet vrcholù neklesne na~danou konstantù~$\ell$. +hrany a kontrahuje je, dokud poèet vrcholù neklesne na~danou konstantu~$\ell$. \s{Algoritmus} $\hbox{\sc Contract}(G_0,\ell)$: \algo @@ -31,7 +31,7 @@ v~grafu~$G$ (a mají nìjaké identifikátory, které kontrakce zachovává). Podobnì je-li v~grafu~$G$ øez neobsahující hranu~$e$, odpovídá mu stejnì velký øez v~$G/e$. Velikost minimálního øezu tedy kontrakcí nikdy neklesne -- mù¾e pouze stoupnout, pokud -zkontrahujeme hranu le¾ící ve~v¹ech minimálních øezech, +skontrahujeme hranu le¾ící ve~v¹ech minimálních øezech, Zvolíme nyní pevnì jeden z~minimálních øezù~$C$ v~zadaném grafu~$G_0$ a oznaèíme~$k$ jeho velikost. Pokud algoritmus ani jednou nevybere hranu le¾ící v~tomto øezu, velikost @@ -64,7 +64,7 @@ mnoho jin zopakujeme $K$-krát a pou¾ijeme nejmen¹í z~nalezených øezù. Ten u¾ bude minimální s~pravdìpodobností $$ -P_K \ge 1 - (1-c/n^2)^K \ge 1 - e^{-cK/n^2} = 1 - e^{-cK/n^2}. +P_K \ge 1 - (1-c/n^2)^K \ge 1 - e^{-cK/n^2}. $$ (Druhá nerovnost platí díky tomu, ¾e $e^{-x} \ge 1-x$ pro v¹echna $x\ge 0$.) Pokud tedy nastavíme poèet opakování~$K$ na $\Omega(n^2)$, mù¾eme tím pravdìpodobnost @@ -86,14 +86,14 @@ matice sousednosti druh mezi $u$ a~$v$. To opìt trvá èas $\O(n)$. Procedura {\sc Contract} tedy pracuje v~èase $\O((n-\ell)\cdot n)$ a celý -$K$-krát ziterovaný algoritmus v~$\O(Kn^2)$. Pokud se spokojíme s~inverznì +$K$-krát ziterovaný algoritmus v~$\O(Kn^2)$. Pokud se spokojíme s~pøevrácenì polynomiální pravdìpodobností chyby, nalezneme minimální øez v~èase $\O(n^4\log n)$. \h{Kargerùv-Steinùv algoritmus} Pøedchozí prostinký algoritmus mù¾eme je¹tì podstatnì vylep¹it. V¹imnìme si, ¾e bìhem kontrahování hran pravdìpodobnost toho, ¾e vybereme \uv{¹patnou} -hranu le¾ící v~minimálním øezu, postupnì rostla z~poèáteèních $2/n^2$ a¾ po obrovské +hranu le¾ící v~minimálním øezu, postupnì rostla z~poèáteèních $2/n$ a¾ po obrovské $2/3$ v~poslední iteraci (pro $\ell=2$). Pomù¾e tedy zastavit kontrahování døíve a~pøejít na~spolehlivìj¹í zpùsob hledání øezu. @@ -150,9 +150,9 @@ $$\eqalign{ z_i+1 &= {z_{i-1}^2 + 2z_{i-1} + 1 \over z_{i-1}}, \cr z_i+1 &= z_{i-1} + 2 + {1\over z_{i-1}}. \cr }$$ -Jeliko¾ $z_0=4$, a~tím pádem $z_i\ge 1$ pro v¹echna~$i$, získáme z~poslední -rovnosti vztah $z_i \le z_{i-1} + 2$, a~tudí¾ $z_i \le 2i+4$. -Zpìtnou substitucí obdr¾íme $g_i \ge 4/(2i+5)$, tedy $p_i \ge g_i = \Omega(1/i)$. +Jeliko¾ $z_0=3$, a~tím pádem $z_i\ge 3$ pro v¹echna~$i$, získáme z~poslední +rovnosti vztah $z_i \le z_{i-1} + 2$, a~tudí¾ $z_i \le 2i+3$. +Zpìtnou substitucí obdr¾íme $g_i \ge 4/(2i+4)$, tedy $p_i \ge g_i = \Omega(1/i)$. Nyní si staèí vzpomenout, ¾e hloubka rekurze èiní $\O(\log n)$, a ihned získáme odhad pro pravdìpodobnost správného výsledku $\Omega(1/\log n)$. Ná¹ algoritmus -- 2.39.2