slama.dev

Aproximační Algoritmy

poznámky · 10. 1. 2022 · 🇨🇿 · dostupné v PDF · [upravit]

• Základní definice
  • Pravděpodobnost v algoritmech
• Metrický TSP
  • Kostrový algoritmus
  • Christofidesův algoritmus
• Quicksort
• Konflikty v distribuovaných systémech
• Globální minimální řez
  • Přímočarý algoritmus
  • Spojující algoritmus
• Rozvrhování
  • Hladový algoritmus
  • Algoritmus lokálního prohledávání
  • Largest Processing Time (LPT)
  • Odbočka: online algoritmy
  • Bin packing
• Hledání disjunktních cest
  • Jednotkové kapacity
  • Nejednotkové kapacity
• Splnitelnost (MAX-SAT)
  • RAND-SAT
  • BIASED-SAT
  • LP-SAT
  • BEST-SAT
• Pokrývací problémy
  • Vrcholové pokrytí
  • Množinové pokrytí
    • $f$-aproximační algoritmy
    • $g$-aproximační algoritmy
  • Maximální nezávislá množina
• Hashovací funkce
  • Dynamický slovník
  • Statický slovník
• Testování
  • Násobení matic
  • Nulovost polynomů (Polynomial Identity Testing)
• Perfektní párování
  • Izolující lemma
• Odkazy

Úvodní informace

Tato stránka obsahuje moje poznámky z přednášky Jiřího Sgalla z akademického roku 2021/2022 (MFF UK). Pokud by byla někde chyba/nejasnost, nebo byste rádi něco přidali, tak stránku můžete upravit pull requestem (případně mi dejte vědět na mail).

Základní definice

Definice (Optimalizační problém) je $\mathcal{I}, \mathcal{F}, f, g$

• $\mathcal{I} \ldots$ množina všech vstupů/instancí
  • množina všech ohodnocených grafů
• $\forall I \in \mathcal{I}: \mathcal{F}(I) \ldots$ množina přípustných řešení
  • pro daný ohodnocený graf všechny kostry
• $\forall I \in \mathcal{I}, A \in \mathcal{F}(I): f(I, A) \ldots$ účelová funkce
  • součet hran na kostře
• $g \ldots$ bit (zda chceme maximalizovat nebo minimalizovat)
  • maximalizujeme

Definice (NP-Optimalizační problém) je $\mathcal{I}, \mathcal{F}, f, g$, pro které platí stejné věci jako pro normální optimalizační problémy, ale navíc

• délka přípustných řešení $\le \mathrm{poly}(|I|)$.
• jazyk dvojic $(I, A), I \in \mathcal{I}, A \in \mathcal{F}(I)$ je v $P$ (rychle umíme ověřit, zda je řešení přípustné)
• $f$ počitatelná v polynomiálním čase

Definice: algoritmus $A$ je $R$-aproximační alg., pokud:

• v polynomiálním čase v $|I|$ na vstupu $I$ najde $A \in \mathcal{F}(I)$
• pro minimalizační problém: $\forall I: f(A) \le R \cdot \mathrm{OPT}(I)$
• pro maximalizační problém: $\forall I: f(A) \ge \mathrm{OPT}(I) / R$

Pravděpodobnost v algoritmech

1. algoritmy s chybou: někdy dělají chybu, ale většinou ji neudělají
2. bez chyb, běží v průměrném čase polynomiálním

• třída $\mathrm{NP}$: jazyky, pro které existuje polynomiální algoritmus $A$, který ověří správnost:
  • $\forall a \in L\ \exists b: A(a, b) = 1$
  • $\forall a \not\in L\ \forall b: A(a, b) = 0$
• třída $\mathrm{RP}$: jazyky, pro které existuje polynomiální algoritmus $A$, který ověří správnost:
  • $\forall a \in L\ \mathrm{Pr}_b\left[A(a, b)\right] \ge \frac{1}{2}$
  • $\forall a \not\in L\ \mathrm{Pr}_b\left[A(a, b)\right] = 0$

Metrický TSP

• Vstup: metrika $V, d$ na úplném ohodnoceném grafu
  • metrika $\equiv$ vrcholy splňují následující:
    1. trojúhelníkova nerovnost
    2. symetrie
    3. $d(x, y) = 0 \iff x = y$
  • pokud by to nebyla metrika, tak poly algoritmus neexistuje (jde převést na normální TSP)
• Výstup: cyklus $C$ na všech vrcholech $V$
• Cíl: minimalizovat $d(C)$

Kostrový algoritmus

Algoritmus (kostrový):

1. najdeme minimální kostru
2. navštívíme všechny vrcholy (například přes DFS), čímž dostaneme tah přes všechny vrcholy
3. zkrátíme ji na cyklus tak, že vynecháme opakující-se vrcholy

Věta: algoritmus je $2$-aproximační.

Důkaz: kostra je nejvýše tak velká, jako optimální řešení a tenhle algoritmus je lepší než $2$ kostry (díky trojúhelníkové nerovnosti a symetrii – procházíme i tam i zpět)

Christofidesův algoritmus

(👀): brát hrany dvakrát je plýtvání – pospojujeme liché vrcholy přes minimální párování, abychom nemuseli chodit tam a zpět

1. najdeme minimální kostru $T$
2. najdeme minimální perfektní párování $M$ na vrcholech s lichými stupni v $T$
   • vždy existuje, jelikož máme úplný graf a vrcholů s lichým stupňem je sudý počet
3. zkrátíme na cyklus $T \cup M$
   • děláme je tak, že vybereme dvě hrany incidentní s vrcholem a nahradíme je za jednu

Věta: algoritmus je $3/2$-aproximační.

Důkaz: $$\mathrm{ALG} \le d(T) + d(M) \le \mathrm{OPT} + \frac{1}{2}\mathrm{OPT}$$

Důkaz $d(M) \le \frac{1}{2}\mathrm{OPT}$ uděláme obrázkem:

Alespoň jeden z párování v cylku bude $\le \frac{1}{2} \mathrm{OPT}$, jelikož celý cyklus je lepší optimální řešení.

Poznámka:

• v realitě se algoritmus chová výrazně lépe, například až k faktoru $1.1$
• dnes umíme $(\frac{3}{2} - \varepsilon)$-aproximaci
• TSP v rovině: existuje $(1 + \varepsilon)$-aproximační schéma (ale stále je $\mathrm{NP}$ těžký)

Quicksort

Algoritmus (quicksort):

1. $|S| \le 1 \ldots$ konec, vystoupíme $S$ (base case)
2. jinak vybereme uniformě náhodně $p \in S$
3. $A = \left\{x \in S \mid x < p\right\}, B = \left\{x \in S \mid x > p\right\}$
   • posloupnost má všechny prvky rozdílné, takže chceme ostrá nerovnítka
4. rekurzivně se zavoláme na $A, B$
5. vystoupíme $A, p, B$

Věta: quicksort má průměrnou časovou složitost $n \cdot \log n$.

Důkaz: počítáme $A_{i, j} = \mathrm{Pr}\left[\text{porovnáme $i$-tý a $j$-tý prvek}\right]$

• zavedeme indikátorové veličiny $X_{i, j} = \begin{cases}1 & A_{i, j}\ \text{nastane} \\ 0 & \text{jinak}\end{cases}$

Lemma: nechť $i < j$. Pak $\mathrm{Pr}\left[A_{i, j}\right] = \frac{2}{j - i + 1}$

Důkaz: to, že se dva prvky porovnají musí znamentat, že jeden z jich byl pivot, ale žádný mezi nimi pivot nebyl (jelikož by je to rozdělilo). Musíme tedy vybrat právě jeden z těchto dvou z intervalu $\left[i, j\right]$, kde je celkově $j - i + 1$ čísel.

Sečtením přes všechny dvojice $i < j$ dostaváme následující: $$\begin{aligned} \mathbb{E}\left[\#\ \text{porovnání}\right] &= \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} X_{i, j} \\ &= \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} \frac{2}{j - i + 1} \\ & = \sum_{i = 1}^{n - 1} \sum_{k = 2}^{n - i} \frac{2}{k} \\ & \cong n \cdot H_n \qquad H_n \ldots \text{harmonická posloupnost}\\ & \cong n \cdot \log n \end{aligned}$$

Konflikty v distribuovaných systémech

• $n$ procesorů se snaží o přístup k jednomu zdroji
• přímá komunikace není možná
• v každém cylku může každý procesor požadovat přístup
  • povede se pouze, když o něho žádá jeden

Algoritmus:

1. v každém cylku zkus s pravděpodobností $p$ přistoupit ke zdroji
   • $p$ si nastavíme tak, aby to vyšlo hezky
2. opakuj, dokud se ti to nepovede

Věta: algoritmus s $p = \frac{1}{n}$ s pravděpodobností alespoň $1 - \frac{1}{n}$ uspěje po $t = 2 en \ln n$ cyklech.

Důkaz: modifikujme algoritmus, aby zkoušel přistupovat i po té, co ho získal (lehčí počítání, které pouze zhorší pravděpodobnost úspěchu).

Nechť $A_{i, r}$ je jev, že $i$-tý proces upěl v $r$-tém cyklu. Pak $$\mathrm{Pr}\left[A_{i, r}\right] = p \cdot \left(1 - p\right)^{n - 1} = \frac{1}{n} \left(1 - \frac{1}{n}\right)^{n - 1} \ge \frac{1}{en}$$

Nyní počítáme $F_{i, t}$ které říká, že $i$-tý proces neuspěje v žádném z $t = 2 en \ln n$ cyklů: $$\mathrm{Pr}\left[F_{i, t}\right] = \prod_{r = 1}^{t} \left(1 - A_{i, r}\right) \le \left(1 - \frac{1}{en}\right)^t = \left(\left(1 - \frac{1}{en}\right)^{en}\right)^{\frac{t}{en}} \le n^{-2}$$

To, že neexistuje proces, který neuspěje, odhadneme jako $$\mathrm{Pr}\left[\bigcup_{i = 1}^{n} F_{i, t}\right] \le \sum_{i = 1}^{n} \mathrm{Pr}\left[F_{i, t}\right] \le n \cdot n^{-2} = n^{-1} = \frac{1}{n}$$

Globální minimální řez

• Vstup: neorientovaný graf $(V, E)$
• Výstup: řez $F \subseteq E$
• Cíl: minimalizovat $|F|$

Přímočarý algoritmus

Algoritmus:

1. převedeme graf na ohodnocený s jednotkovými cenami
2. zafixujeme vrchol $s$
3. pro všechny ostatní vrcholy $t$ najdeme minimalní $s-t$ řez
4. vrátíme minimum

• umíme vyřešit řádové v $\mathcal{O}(n^3)$

Spojující algoritmus

Algoritmus:

1. vybereme náhodnou hranu a její vrcholy spojíme do jednoho
2. opakujeme, dokud nemáme pouze dva vrcholy
3. zbylé hrany na konci jsou náš řez

• idea je to, že hran v minimálním řezu je málo a nejspíš se do nich netrefíme
• pracujeme s multigrafy – při kontrakci zachováváme hrany
• umíme ho implementovat rychle (řádově $\mathcal{O}(n^2 \cdot \log n)$)
• opravdu produkuje řez, protože vrcholy mezi výslednými komponentami danými vrcholy nemizí

(👀): multigraf s $n$ vrcholy a min. řezem velikosti $k$ má alespoň $nk/2$ hran.

• každý vrchol sám o sobě tvoří řez, pak stačí přes všechny posčítat…

Věta: pravděpodobnost, že najdeme daný minimální řez $C$ je alespoň $\binom{n}{2}^{-1} = \frac{2}{n \cdot (n - 1)}$.

Důkaz: nechť $A_i$ jev, že v prvních $i$ iteracích jsme nevybrali hranu z $C$.

• $\mathrm{Pr}[A_0] = 1$ (žádnou jsme ještě nevybrali)
• $\mathrm{Pr}[A_1] \ge 1 - \frac{k}{nk / 2} = 1 - \frac{2}{n}$
• $\mathrm{Pr}[A_2 \mid A_1] \ge 1 - \frac{k}{(n-1)k/2} = 1 - \frac{2}{n - 1}$
• $\mathrm{Pr}[A_2] = \mathrm{Pr}[A_2 \mid A_1] \cdot \mathrm{Pr}\left[A_1\right]$, z čehož vyplývá:

$$\begin{aligned} \mathrm{Pr}[A_{n - 2}] & \ge \left(1 - \frac{2}{n}\right) \left(1 - \frac{2}{n -1}\right) \ldots \left(1 - \frac{2}{3}\right) \\ &= \frac{n - 2}{n} \frac{n - 3}{n - 1} \frac{n - 4}{n - 2} \ldots \frac{2}{4} \frac{1}{3} \\ &= \frac{2}{n \cdot (n - 1)} = \frac{1}{\binom{n}{2}} = \binom{n}{2}^{-1} \end{aligned}$$

Důsledek: každý graf $G$ má $\le \binom{n}{2}$ globálních minimálních řezů.

• jeden takový je například cyklus $k = 2$ – ten má opravdu řádově tolik řezů

Důkaz: každý běh algoritmu vystoupí právě jeden řez. Kdyby jich bylo více, tak nám pravděpodobnost nevychází (jevy jsou disjunktní).

(👀): Pro $n^2$ opakování algoritmu výše dostáváme nejmenší řez s pravděpodobností $\ge \frac{1}{2}$

Poznámka: algoritmus můžeme vylepšit tak, že části, ve kterých se nejvíce dělají chyby (konkrétně ty pozdější) opakujeme vícekrát (a vezmeme minimum).

Rozvrhování

• Vstup: $m$ strojů, $n$ úloh, každá o délce $p_i$
• Výstup: rozklad $\left\{1, \ldots, n\right\} = I_1 \cup I_2 \cup \ldots \cup I_m$ (rozvržení úloh na stroje)
• Cíl: minimalizovat $\max_{i=1}^{m} \sum_{j \in I_i}^{p_j}$ (délka nejdelšího stroje)

Hladový algoritmus

Algoritmus (hladový):

1. úlohu přidej vždy tam, kde jich je zatím nejméně
2. profit?

Věta (slabší odhad): hladový rozvrhovací algoritmus je $2$-aproximační.

Důkaz: uvažme následující diagram:

Z obrázku vyplývá:

• $T \le \mathrm{OPT}$ (optimum muselo úlohy také někam dát)
• $p_j \le \mathrm{OPT}$ (optimum $p_j$ muselo použít)

Spojením dostáváme $\mathrm{ALG} = T + p_j \le 2 \cdot \mathrm{OPT}$

Věta (silnější odhad): hladový rozvrhovací algoritmus je $\left(2 - \frac{1}{m}\right)$-aproximační.

Důkaz:

• $\frac{1}{m} \sum_{k = 1}^{n} p_k \le \mathrm{OPT}$
  • lépe, než rovnoměrně všechny úlohy rozvrhnout nemůžeme
• $\sum_{k = 1}^{n} p_k \ge m \cdot T + p_j$
  • součet všech úloh je alespoň součet před $T$ + posledí úloha (vynechám „ocásky“)

Kombinací nerovností dostávám $T + \frac{p_j}{m} \le \mathrm{OPT}$.

Nyní místo odhadu $T \le \mathrm{OPT}$ použijeme tyto dva odhady:

$$\begin{aligned} T + \frac{p_j}{m} &\le \mathrm{OPT} \\ (p_j &\le \mathrm{OPT}) \cdot \left(1 - \frac{1}{m}\right) \end{aligned}$$

Součtem dostáváme

$$\begin{aligned} T + \frac{p_j}{m} + \left(1 - \frac{1}{m}\right) p_j &\le \mathrm{OPT} + \left(1 - \frac{1}{m}\right) \mathrm{OPT} \\ \mathrm{ALG} &\le \left(2 - \frac{1}{m}\right) \mathrm{OPT} \end{aligned}$$

Algoritmus lokálního prohledávání

Pro lokální algoritmus potřebujeme s rozvrhem pracovat formálněji:

• Vstup: $m$ strojů, $n$ úloh, každá o délce $p_i$
• Výstup: funkce přiřazující každé úloze startovní čas $s_i$, koncový čas $c_i$ a stroj $i$
  • musí platit že $c_i = s_i + p_i$ a že se úlohy nepřekrývají
• Cíl: minimalizovat $\max_{i=1}^{m} \sum_{j \in I_i}^{p_j}$ (délka nejdelšího stroje)

Algoritmus (lokální prohledávání):

1. najdi libovolný rozvrh bez mezer (i na začátku)
2. vezmi libovolné $j$ s maximálním $c_j$
   • pokud existuje stroj $i$ s délkou rozvrhu $< s_j$, tak přesuň $j$ na $i$ s minimální délkou
   • jinak vystup aktuální rozvrh

(👀): $c_{\min} neklesá$

(👀): Každou úlohu přesuneme nejvýše jednou.

Důkaz: jelikož ji přesouváme na stroj s minimální délkou, tak by musel existovat nějaký s ještě menší, což by byl spor s tím, jak algoritmus funguje (dáváme na nejmenší).

Důsledek: algoritmus je polynomiální.

Věta (silnější odhad pro lokální algoritmus): algoritmus je $\left(2 - \frac{1}{m}\right)$-aproximační.

Largest Processing Time (LPT)

Algoritmus (LPT):

1. úlohy uspořádáme tak, že $p_1 \ge p_2 \ge \ldots \ge p_n$
2. použijeme hladový algoritmus

Věta: LPT je $\left(\frac{4}{3} - \frac{1}{3m}\right)$-aproximační algoritmus.

Důkaz: BUNO předpokládejme, že $p_n$ určuje délku rozvrhu (kdyby ne tak na další úlohy zapomenu a řešení se tím nezmění). Rozlišíme $2$ případy:

• $p_n \le \frac{1}{3} \mathrm{OPT}$ – stejný výpočet jako předtím, jen silnější nerovnost:
  • $\mathrm{ALG} = T + p_n$, $T + \frac{p_n}{m} \le \mathrm{OPT}$
  • stejným výpočtem jako předtím máme $\mathrm{ALG} \le \mathrm{OPT} + \left(1 - \frac{1}{m}\right) \frac{1}{3} \mathrm{OPT}$
• $p_n > \frac{1}{3} \mathrm{OPT}$ – LPT vygeneruje optimální rozvrh
  • víme, že délka poslední, a tedy každé úlohy je alespoň $\mathrm{OPT} / 3$
  • žádný počítač nebude mít 3 úlohy, jelikož by pak byl větší než optimum
  • chceme argumentovat, že LPT udělá stejné dvojice jako optimální rozvrh:
    • $p_m + p_{m + 1} \le \mathrm{OPT}$ – uvážíme-li pouze prvních $m + 1$ úloh, tak optimální rozvrh bude mít alespoň $2$ na jednom počítači a ty rozhodně nebudou kratší než dvě nejkratší
      • tento rozvrh s méně úlohami je jistě $\le \mathrm{OPT}$, proto nerovnost platí
    • $p_{m - 1} + p_{m + 2} \le \mathrm{OPT}$ – v optimálním rozvrhu budou mít alespoň $2$ počítače dvojici úloh; v jedné z nich bude čtvrtá nejmenší ($p_{m - 1}$), která tam bude s nejmenší ($p_{m + 2}$)
    • obdobně dostaneme všechny další dolní odhady…

Odbočka: online algoritmy

• vstup přichází postupně
• řešení musíme konstruovat postupně po krocích a pak už neměníme
• hladový je online, lokální prohledávání není
• pro $m = 2$: lepší než $3/2$-aproximační neexistuje (úlohy délky $\left\{1, 1, 2\right\}$)
• pro $m = 3$ je opět hladový nejlepší
• pro $m > 3$ to už tak není (existují lepší)

Bin packing

• Vstup: $a_1, \ldots, a_n \ge 0$
• Výstup: rozklad $\left\{1, \ldots, n\right\} = I_1 \cup \ldots \cup I_m$ tak, že $\forall i: \sum_{j \in I_i} a_j \le 1$
  • součet věcí v každém koši může být nejvýše $1$
• Cíl: minimalizovat $m$ (počet košů)

Algoritmus (first fit): dej $a_j$ do prvního koše, do kterého se vejde.

Algoritmus (best fit): dej $a_j$ do nejplnějšího koše, do kterého se vejde.

Věta: oba algoritmy jsou $1.7$-aproximační (a je to těsný odhad).

Věta: Je NP těžké najít $R$-aproximační algoritmus pro $R \le 3/2$

Důkaz: Je NP těžké rozhodnout, zda $\mathrm{OPT} = 2$, jelikož pomocí něho můžeme přímočaře vyřešit problém dělení množiny na dvě časti se stejným součtem (nastavíme velikost košů na tenhle součet), což je NP těžké.

Věta: Existuje asymptotické aproximační schéma, t. j. $$(\forall \varepsilon) (\exists \mathrm{ALG}) (\forall I) \mathrm{ALG}(I) \le (1 + \varepsilon)\mathrm{OPT}(I) + 1$$

Algoritmus (any fit): dej $a_j$ do nějakého neprázdného koše; pokud nelze, dej ho do nového.

• zahrnuje jak best fit, tak first fit

Věta: každý any fit algoritmus má aproximační poměr $\le 2$.

Důkaz: Pro $\mathrm{OPT} = 1$ triviální. Jinak nechť $B_i = \sum_{j \in I_i} a_j$. Musí platit, že $(\forall i, j, i \neq j) B_i + B_j > 1$ (jinak spor s během algoritmu). Posčítáním pro všechny dvojice dostáváme $$\frac{m}{2} < \sum_{i = 1}^{m} B_i = \sum_{j = 1}^{n} a_j \le \mathrm{OPT}$$

Hledání disjunktních cest

• Vstup:
  • graf $G = (V, E)$ (orientovaný/neorientovaný)
  • dvojice vrcholů $(s, t), \ldots, (s_k, t_k)$
  • kapacita hran $c$
• Výstup:
  • $I \subseteq \left\{1, \ldots, k\right\}$ (dvojice které spojíme cestou)
  • cesty $P_i, i \in I, P_i$ cesta z $s_i$ do $t_i$ tak, že každá hrana $e \in E$ leží na nejvýše $c$ cestách $P_i$
• Cíl: minimalizovat $|I|$

Jednotkové kapacity

Algoritmus (hladový):

1. najdeme nejkratší cestu mezi nespojenou dvojicí (přes všechna $i$)
   • pokud neexistuje, tak vystoupíme
2. odebereme použité hrany

(👀): hladový algoritmus nemá aproximační poměr lepší než $\mathcal{O}(\sqrt{m})$:

Délka $s_1 \mapsto t_1$ je $\mathcal{O}(k)$. Abychom tuto cestu nezvolili, tak musejí mít ostatní alespoň $\mathcal{O}(k)$ hran a celkově jich tedy musí být řádově $m = \mathcal{O}(k^2)$. Naše řešení je tedy o $k = \mathcal{O}(\sqrt{m})$ horší.

Věta: Hladový algoritmus s $c = 1$ je $\mathcal{O}\left(\sqrt{m}\right)$-aproximační.

Důkaz: BUNO $\mathrm{OPT} \ge 1$ (jinak bychom hned skončili)

• pak $|I| = \mathrm{ALG} \ge 1$ (také nějakou najdeme)

Nechť $I^*, \left\{P_i^* \mid i \in I^*\right\}$ je optimum. Počítejme cesty:

• dlouhé cesty: $|P_i^*| > \sqrt{m}$
  • je jich $\le \sqrt{m}$ (jinak bych měl více než $m$ hran)
  • ty mi tedy nic nekazí, jelikož nám stačí, že algoritmus najde nějakou cestu
• krátké cesty:
  • $i \in I \ldots\$ vše ok
  • $i \not\in I \ldots\ P_i^*$ má nějakou společnou hranu s nějakou cestou $P_j$ t. ž. $|P_j| \le \sqrt{m}$
    • ve chvíli, kdy algoritmus poprvé vybral cestu delší než $\sqrt{m}$ už nemohl vybrat $P_i^*$, protože tu blokovala nějaká cesta, kterou již předtím zvolil (a ta musí být krátká)

Tedy počet krátkých cest $P_i^* \le |I| \left(\sqrt{m} + 1\right)$

• $1$ – náš algoritmus a optimum vybrali stejnou cestu
• $\sqrt{m}$ – krátká cesta v našem řešení zablokuje nejvýše $\sqrt{m}$ ostatních krátkých $$\mathrm{OPT} = |I^*| \le \underbrace{\sqrt{m}}_{\text{dlouhé}} + \underbrace{|I| \left(\sqrt{m} + 1\right)}_{\text{krátké}} \le \mathcal{O}(\sqrt{m}) |I| = \mathcal{O}(\sqrt{m}) \mathrm{ALG}$$

Nejednotkové kapacity

Algoritmus (hladový pro nejednotkovou kapacitu):

1. zvolíme $\beta = \left\lceil m^{\frac{1}{c + 1}} \right\rceil$
2. najdeme nejkratší cestu mezi nespojenou dvojicí (přes všechna $i$)
   • pokud neexistuje nebo $d(P_i) \ge \beta^c$