slama.dev

Aproximační Algoritmy

poznámky  Icon, vydáno 10. 1. 2022, aktualizováno 15. 10. 2022; dostupné v [PDF]

Úvodní informace

Tato stránka obsahuje moje poznámky z přednášky Jiřího Sgalla z akademického roku 2021/2022. Pokud by byla někde chyba/nejasnost, nebo byste rádi někam přidali obrázek/text, 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 I,F,f,g\mathcal{I}, \mathcal{F}, f, g

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

Pro minimalizační zajišťujeme, že naše je vždy dostatečně malé.

Pro maximalizační zajišťujeme, že je vždy dostatečně velké.

Definice: algoritmus AA je RR-aproximační alg., pokud:

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

Metrický TSP

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 22-aproximační.

Důkaz: kostra je nejvýše tak velká, jako optimální řešení a tenhle algoritmus je lepší než 22 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 TT
  2. najdeme minimální perfektní párování MM na vrcholech s lichými stupni v TT
    • 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 TMT \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/23/2-aproximační.

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

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

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

Poznámka:

Quicksort

Algoritmus (quicksort):

  1. S1|S| \le 1 \ldots konec, vystoupíme SS (base case)
  2. jinak vybereme uniformě náhodně pSp \in S
  3. A={xSx<p},B={xSx>p}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,BA, B
  5. vystoupíme A,p,BA, p, B

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

Pro připomenutí:

  • E[Xi,j]=Pr[Ai,j]\mathbb{E}\left[X_{i, j}\right] = \mathrm{Pr}\left[A_{i, j}\right] (indikátorová veličina)
  • E[X+Y]=E[X]+E[Y]\mathbb{E}\left[X + Y\right] = \mathbb{E}\left[X\right] + \mathbb{E}\left[Y\right]

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

Lemma: nechť i<ji < j. Pak Pr[Ai,j]=2ji+1\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 [i,j]\left[i, j\right], kde je celkově ji+1j - i + 1 čísel.

Sečtením přes všechny dvojice i<ji < j dostaváme následující: E[# porovnaˊnıˊ]=i=1n1j=i+1nXi,j=i=1n1j=i+1n2ji+1=i=1n1k=2ni2knHnHnharmonickaˊ posloupnostnlogn \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

Algoritmus:

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

Věta: algoritmus s p=1np = \frac{1}{n} s pravděpodobností alespoň 11n1 - \frac{1}{n} uspěje po t=2enlnnt = 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ť Ai,rA_{i, r} je jev, že ii-tý proces upěl v rr-tém cyklu. Pak Pr[Ai,r]=p(1p)n1=1n(11n)n11en\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 Fi,tF_{i, t} které říká, že ii-tý proces neuspěje v žádném z t=2enlnnt = 2 en \ln n cyklů: Pr[Fi,t]=r=1t(1Ai,r)(11en)t=((11en)en)tenn2\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 Pr[i=1nFi,t]i=1nPr[Fi,t]nn2=n1=1n\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

Přímočarý algoritmus

Algoritmus:

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

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

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

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

Důkaz: nechť AiA_i jev, že v prvních ii iteracích jsme nevybrali hranu z CC.

Pr[An2](12n)(12n1)(123)=n2nn3n1n4n22413=2n(n1)=1(n2)=(n2)1 \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 GG(n2)\le \binom{n}{2} globálních minimálních ř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 n2n^2 opakování algoritmu výše dostáváme nejmenší řez s pravděpodobností 12\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í

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 22-aproximační.

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

Z obrázku vyplývá:

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

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

Důkaz:

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

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

T+pjmOPT(pjOPT)(11m) \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

T+pjm+(11m)pjOPT+(11m)OPTALG(21m)OPT \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:

Prostě přesouváme stroje, které končí nejpozději někam, aby začínaly dříve a zlepšujeme tím maximum.

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

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

(👀): cminneklesaˊ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 (21m)\left(2 - \frac{1}{m}\right)-aproximační.

Largest Processing Time (LPT)

Algoritmus (LPT):

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

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

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

Odbočka: online algoritmy

Bin packing

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

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

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

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

Důkaz: Je NP těžké rozhodnout, zda OPT=2\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. (ε)(ALG)(I)ALG(I)(1+ε)OPT(I)+1(\forall \varepsilon) (\exists \mathrm{ALG}) (\forall I) \mathrm{ALG}(I) \le (1 + \varepsilon)\mathrm{OPT}(I) + 1

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

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

Důkaz: Pro OPT=1\mathrm{OPT} = 1 triviální. Jinak nechť Bi=jIiajB_i = \sum_{j \in I_i} a_j. Musí platit, že (i,j,ij)Bi+Bj>1(\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 m2<i=1mBi=j=1najOPT\frac{m}{2} < \sum_{i = 1}^{m} B_i = \sum_{j = 1}^{n} a_j \le \mathrm{OPT}

Hledání disjunktních cest

Jednotkové kapacity

Algoritmus (hladový):

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

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

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

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

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

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

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

Nejednotkové kapacity

Algoritmus (hladový pro nejednotkovou kapacitu):

  1. zvolíme β=m1c+1\beta = \left\lceil m^{\frac{1}{c + 1}} \right\rceil
  2. najdeme nejkratší cestu mezi nespojenou dvojicí (přes všechna ii)
    • pokud neexistuje nebo d(Pi)βcd(P_i) \ge \beta^c, vystoupíme
  3. přenásobíme délku hran nejkratší cesty faktorem β\beta