\input lecnotes.tex
\prednaska{9}{Co si poèít s tì¾kým problémem}{}

V~pøedchozí kapitole jsme zjistili, ¾e leckteré rozhodovací problémy
jsou \NP-úplné. Z~toho plyne, ¾e jsou ekvivalentní, ale bohu¾el také,
¾e ani jeden z~nich zatím neumíme vyøe¹it v~polynomiálním èase.

Èasto se stane, ¾e problém, který v~¾ivotì potkáme, patøí mezi \NP-úplné.
Pøesnìji øeèeno spí¹ ne¾ s~rozhodovacím problémem se potkáme s~problémem
{\I optimalizaèním,} ve~kterém jde o~nalezení {\I nejlep¹ího} objektu
s~danou vlastností. To mù¾e být tøeba nejvìt¹í nezávislá mno¾ina v~grafu
nebo obarvení grafu nejmen¹ím mo¾ným poètem barev. Kdybychom umìli efektivnì
øe¹it optimalizaèní problém, umíme samozøejmì øe¹it i pøíslu¹ný rozhodovací,
tak¾e pokud $\P\ne\NP$, jsou i optimalizaèní problémy tì¾ké.

Ale co naplat, svìt nám takové úlohy pøedkládá a my je potøebujeme vyøe¹it.
Na¹tìstí situace není zase tak beznadìjná. Nabízejí se tyto mo¾nosti, co si
poèít:

\numlist\ndotted
\:{\I Spokojit se s~málem.} Nejsou vstupy, pro které problém potøebujeme
  øe¹it, dostateènì malé, abychom si mohli dovolit pou¾ít algoritmus
  s~exponenciální slo¾itostí? Zvlá¹» kdy¾ takový algoritmus vylep¹íme
  proøezáváním neperspektivních vìtví výpoètu a tøeba ho i paralelizujeme.
\:{\I Vyøe¹it speciální pøípad.} Nemají na¹e vstupy nìjaký speciální
  tvar, kterého bychom mohli vyu¾ít? Grafové problémy jsou èasto v~\P{}
  tøeba pro stromy nebo i obecnìji pro bipartitní grafy. U~èíselných
  problémù zase nìkdy pomù¾e, jsou-li èísla na vstupu dostateènì malá.
\:{\I Øe¹ení aproximovat.} Opravdu potøebujeme optimální øe¹ení? Nestaèilo
  by nám o~kousíèek hor¹í? Èasto existuje polynomiální algoritmus, který
  nalezne nejhùøe $c$-krát hor¹í øe¹ení ne¾ je optimum, kde $c$~je konstanta.
\:{\I Pou¾ít heuristiku.} Neumíme-li nic lep¹ího, mù¾eme sáhnout po~nìkteré
  z~mnoha heuristických technik, které sice nic nezaruèují, ale obvykle
  nìjaké uspokojivé øe¹ení najdou. Mù¾e pomoci tøeba hladový algoritmus
  nebo genetické algoritmy. Èasto platí, ¾e èím déle heuristiku necháme
  bì¾et, tím lep¹í øe¹ení najde.
\:{\I Kombinace pøístupù.} Mnohdy lze pøedchozí pøístupy kombinovat:
  napøíklad pou¾ít aproximaèní algoritmus a poté jeho výsledek
  je¹tì heuristicky vylep¹ovat. Tak získáme øe¹ení, které od~optima
  zaruèenì není moc daleko, a~pokud budeme mít ¹tìstí, bude se od~nìj li¹it
  jen velmi málo.
\endlist

\>Nyní si nìkteré z~tìchto technik pøedvedeme na konkrétních pøíkladech.

\h{Nejvìt¹í nezávislá mno¾ina ve stromu}

Uká¾eme, ¾e hledání nejvìt¹í nezávislé mno¾iny je snadné, pokud graf je strom.

\s{Lemma:} Buï~$T$ zakoøenìný strom a $\ell$ jeho libovolný list. Pak alespoò jedna
z~nejvìt¹ích nezávislých mno¾in obsahuje~$\ell$.

\proof
Mìjme nejvìt¹í nezávislou mno¾inu~$M$, která list~$\ell$ neobsahuje. Podívejme
se na otce~$p$ listu~$\ell$ (kdyby neexistoval, je celý strom jednovrcholový
a tvrzení triviální). Le¾í~$p$ v~$M$? Pokud ne, mohli bychom do~$M$ pøidat
list~$\ell$ a dostali bychom vìt¹í nezávislou mno¾inu. V~opaèném pøípadì z~$M$
odebereme otce~$p$ a nahradíme ho listem~$\ell$, èím¾ dostaneme stejnì velkou
nezávislou mno¾inu obsahující~$\ell$.
\qed

Algoritmus bude pøímoèaøe pou¾ívat toto lemma. Dostane na vstupu strom,
ten zakoøení a zvolí libovolný list. Tento list umístí do nezávislé mno¾iny
a jeho otce odebere, proto¾e se nemù¾e v~nezávislé mno¾inì vyskytovat.
Toto bude opakovat, dokud nìjaké vrcholy zbývají. (Graf se v~prùbìhu mù¾e
rozpadnout na více komponent, ale to nevadí.)

Tento algoritmus jistì pracuje v~polynomiálním èase. ©ikovnou implementací
mù¾eme slo¾itost sní¾it a¾ na lineární. Napøíklad tak, ¾e budeme udr¾ovat seznam
listù. My si uká¾eme jinou lineární implementaci zalo¾enou na prohledávání do hloubky.
Bude pracovat s~polem znaèek~$M$, v~nìm¾ na poèátku bude v¹ude \<false> a postupnì
obdr¾í \<true> v¹echny prvky hledané nezávislé mno¾iny.

\algo{NzMnaVeStromu}
\algin Strom~$T$ s~koøenem~$v$, pole znaèek~$M$.
\:$M[v] \= \<true>$.
\:Pokud je~$v$ list, skonèíme.
\:Pro v¹echny syny~$w$ vrcholu~$v$:
\::Zavoláme se rekurzivnì na podstrom s~koøenem~$w$.
\::Pokud $M[w]=\<true>$, polo¾íme $M[v] \= \<false>$.
\endalgo

\h{Barvení intervalového grafu}

Mìjme~$n$ pøedná¹ek s~urèenými èasy zaèátku a konce. Chceme je rozvrhnout
do co~nejmen¹ího poètu poslucháren tak, aby nikdy neprobíhaly dvì pøedná¹ky
naráz v~jedné místnosti.

Chceme tedy obarvit co nejmen¹ím poètem barev graf, jeho¾ vrcholy jsou èasové
intervaly a dvojice intervalù je spojena hranou, pokud má neprázdný prùnik.
Takovým grafùm se øíká {\I intervalové} a pro jejich barvení existuje pìkný
polynomiální algoritmus.

Podobnì jako jsme geometrické problémy øe¹ili zametáním roviny, zde budeme
\uv{zametat pøímku bodem}, tedy procházet ji zleva doprava, a~v¹ímat si
událostí, co¾ budou zaèátky a konce intervalù. Pro jednoduchost pøedpokládejme,
¾e v¹echny souøadnice zaèátkù a koncù jsou navzájem rùzné.

Kdykoliv interval zaène, pøidìlíme mu barvu. A¾ skonèí, o~barvì si poznamenáme,
¾e je momentálnì volná, a~dal¹ím intervalùm budeme pøednostnì pøidìlovat
volné barvy. Øeèeno v~pseudokódu:

\algo{BarveníIntervalù}
\algin Intervaly $\left[ x_1, y_1 \right], \ldots, \left[ x_n, y_n \right]$.
\:$b \= 0$ \cmt{poèet zatím pou¾itých barev}
\:$B \= \emptyset$ \cmt{které barvy jsou momentálnì volné}
\:Setøídíme mno¾inu v¹ech $x_i$ a $y_i$.
\:Procházíme v¹echna $x_i$ a $y_i$ ve~vzestupném poøadí:
\::Narazíme-li na $x_i$:
\:::Je-li $B\ne\emptyset$, odebereme jednu barvu z~$B$ a ulo¾íme ji do~$c_i$.
\:::Jinak $b\=b+1$ a $c_i\=b$.
\::Narazíme-li na $y_i$:
\:::Vrátíme barvu $c_i$ do~$B$.
\algout Obarvení $c_1,\ldots,c_n$.
\endalgo

\s{Analýza:}
Tento algoritmus má èasovou slo¾itost $\O(n\log n)$ kvùli tøídìní souøadnic.
Samotné obarvování je lineární.

Je¹tì ov¹em potøebujeme dokázat, ¾e jsme pou¾ili minimální mo¾ný poèet barev.
Uva¾ujme okam¾ik, kdy promìnná~$b$ naposledy vzrostla. Tehdy zaèal interval
a mno¾ina~$B$ byla prázdná, co¾ znamená, ¾e jsme $b-1$ pøedchozích barev museli
pøidìlit intervalùm, je¾ zaèaly a dosud neskonèily. Existuje tedy $b$ rùzných
intervalù, které mají spoleèný bod (v~grafu tvoøí kliku), tak¾e ka¾dé obarvení
potøebuje alespoò~$b$ barev.

\h{Problém batohu s~malými èísly}

Pøipomeòme si {\I problém batohu.} Jeho optimalizaèní verze vypadá takto:
Je dána mno¾ina $n$~pøedmìtù s~hmotnostmi $h_1,\ldots,h_n$ a cenami $c_1,\ldots,c_n$
a nosnost batohu~$H$. Hledáme podmno¾inu pøedmìtù~$P \subseteq \{1,\ldots,n\}$,
která se vejde do batohu (tedy $h(P)=\sum_{i\in P} h_i \le H$) a její cena
$c(P) = \sum_{i\in P} c_i$ je nejvìt¹í mo¾ná.

Uká¾eme algoritmus, jeho¾ èasová slo¾itost bude polynomiální v~poètu
pøedmìtù~$n$ a souètu v¹ech cen $C=\sum_i c_i$.

Pou¾ijeme dynamické programování. Pøedstavme si problém omezený na~prvních~$k$
pøedmìtù. Oznaème $A_k(c)$ (kde $0\le c\le C$) minimum z~hmotností tìch podmno¾in
jejich¾ cena je právì~$c$; pokud ¾ádná taková podmno¾ina neexistuje, polo¾íme $A_k(c)=\infty$.

Tato $A_k$ spoèteme indukcí podle~$k$: Pro $k=0$ je
urèitì $A_0(0)=0$ a $A_0(1)=\ldots=A_0(C)=\infty$. Pokud ji¾ známe
$A_{k-1}$, spoèítáme $A_k$ následovnì: $A_k(c)$ odpovídá nìjaké podmno¾inì
pøedmìtù z~$1,\ldots,k$. V~této podmno¾inì jsme buïto $k$-tý pøedmìt nepou¾ili,
a~pak je $A_k(c)=A_{k-1}(c)$, nebo pou¾ili, a~tehdy bude $A_k(c) =
A_{k-1}(c-c_k) + h_k$ (to samozøejmì jen pokud $c\ge c_k$). Z~tìchto dvou
mo¾ností si vybereme tu, která dává mno¾inu s~men¹í hmotností:
$$
A_k(c) = \min (A_{k-1}(c), A_{k-1}(c-c_k) + h_k).
$$
Pøechod od $A_{k-1}$ k~$A_k$ tedy trvá $\O(C)$, od~$A_1$ a¾ k~$A_n$ se dopoèítáme v~èase $\O(Cn)$.

Jakmile získáme~$A_n$, známe pro ka¾dou cenu pøíslu¹nou nejlehèí podmno¾inu.
Maximální cena mno¾iny, která se vejde do batohu, je tedy nejvìt¹í~$c^*$, pro nì¾
je $A_n(c^*) \le H$. Jeho nalezení nás stojí èas $\O(C)$.

Zbývá zjistit, které pøedmìty do~nalezené mno¾iny patøí. Upravíme algoritmus,
aby si pro ka¾dé $A_k(c)$ pamatoval je¹tì $B_k(c)$, co¾ bude index posledního pøedmìtu,
který jsme do~pøíslu¹né mno¾iny pøidali. Pro nalezené $c^*$ tedy bude $i=B_n(c^*)$
poslední pøedmìt v~nalezené mno¾inì, $i'=B_{i-1}(c^*-c_i)$ ten pøedposlední
a tak dále. Takto v~èase $\O(n)$ rekonstruujeme celou mno¾inu od~posledního
prvku k~prvnímu.

Máme tedy algoritmus, který vyøe¹í problém batohu v~èase $\O(nC)$. Tato funkce
ov¹em není polynomem ve~velikosti vstupu, jeliko¾ reprezentujeme-li vstup binárnì,
$C$~mù¾e být a¾ exponenciálnì velké vzhledem k~délce jeho zápisu. To je pìkný
pøíklad tzv. {\I pseudopolynomiálního} algoritmu, tedy algoritmu, jeho¾ slo¾itost
je polynomem v~poètu èísel na vstupu a jejich velikosti. Pro nìkteré \NP-úplné
problémy takové algoritmy existují, pro jiné (napø. pro nezávislou mno¾inu) by
z~jejich existence plynulo $\P=\NP$.

\s{Verze bez cen:} Jednodu¹¹í verzi problému batohu, která nerozli¹uje mezi
hmotnostmi a cenami, zvládneme i jiným algoritmem, opìt zalo¾eným na dynamickém
programování.

Indukcí podle~$k$ vytváøíme  mno¾iny~$Z_k$ obsahující v¹echny hmotnosti
men¹í ne¾~$H$, kterých nabývá nìjaká podmno¾ina prvních~$k$ prvkù. Jistì je $Z_0=\{0\}$.
Podobnou úvahou jako v~pøedchozím algoritmu dostaneme, ¾e ka¾dou dal¹í~$Z_k$ mù¾eme
zapsat jako sjednocení $Z_{k-1}$ s~kopií $Z_{k-1}$ posunutou o~$h_k$, ignorujíce hodnoty
vìt¹í ne¾~$H$. Nakonec ze~$Z_n$ vyèteme výsledek.

V¹echny mno¾iny pøitom mají nejvý¹e~$H+1$ prvkù, tak¾e pokud si je budeme udr¾ovat
jako setøídìné seznamy, spoèítáme sjednocení sléváním v~èase $\O(H)$ a celý algoritmus
dobìhne v~èase $\O(Hn)$.

\h{Aproximace problému obchodního cestujícího}

V~{\I problému obchodního cestujícího} je zadán neorientovaný graf~$G$, jeho¾
hrany jsou ohodnoceny délkami $\ell(e)\ge 0$. V~tomto
grafu chceme nalézt nejkrat¹í z~hamiltonovských kru¾nic, tedy tìch, které nav¹tíví
v¹echny vrcholy.

Není pøekvapivé, ¾e tento problém je tì¾ký -- u¾ sama existence hamiltonovské
kru¾nice je \NP-úplná. Uká¾eme ov¹em, ¾e pokud je graf úplný a platí v~nìm trojúhelníková
nerovnost (tj. $\ell(x,z) \le \ell(x,y) + \ell(y,z)$ pro v¹echny trojice vrcholù $x,y,z$),
mù¾eme problém obchodního cestujícího 2-aproximovat, tedy najít v~polynomiálním
èase kru¾nici, která je pøinejhor¹ím dvakrát del¹í ne¾ ta optimální.

Grafy s~trojúhelníkovou nerovností pøitom nejsou nijak neobvyklé -- odpovídají
toti¾ koneèným metrickým prostorùm.

Algoritmus bude snadný: Najdeme nejmen¹í kostru a obchodnímu cestujícímu poradíme,
a» ji obejde. To mù¾eme popsat napøíklad tak, ¾e kostru zakoøeníme, prohledáme ji
do hloubky a zaznamenáme, jak jsme procházeli hranami. Ka¾dou hranou kostry pøitom
projdeme dvakrát -- jednou dolù, podruhé nahoru. Tím v¹ak nedostaneme kru¾nici,
nýbr¾ jen nìjaký uzavøený sled, proto¾e vrcholy nav¹tìvujeme vícekrát. Sled tedy
upravíme tak, ¾e kdykoliv se dostává do ji¾ nav¹tíveného vrcholu, pøeskoèí ho
a pøesune se a¾ do nejbli¾¹ího dal¹ího nenav¹tíveného. Tím ze sledu vytvoøíme
hamiltonovskou kru¾nici a jeliko¾ v~grafu platí trojúhelníková nerovnost,
celková délka nevzrostla. (Poøadí vrcholù na kru¾nici mù¾eme získat také tak,
¾e bìhem prohledávání budeme vypisovat vrcholy v~preorderu. Rozmyslete si,
¾e je toté¾.)

\s{Vìta:} Nalezená kru¾nice není del¹í ne¾ dvojnásobek optima.

\proof
Oznaème $T$ délku minimální kostry, $A$ délku kru¾nice vydané na¹ím algoritmem
a $O$ (optimum) délku nejkrat¹í hamiltonovské kru¾nice. Z~toho, jak jsme kru¾nici
vytvoøili, víme, ¾e $A\le 2T$. Platí ov¹em také $T\le O$, jeliko¾ z~ka¾dé
hamiltonovské kru¾nice vznikne vynecháním hrany kostra a ta nemù¾e být men¹í
ne¾ minimální kostra. Slo¾ením obou nerovností získáme $A\le 2T\le 2O$.
\qed

Sestrojili jsme tedy 2-aproximaèní algoritmus pro problém obchodního cestujícího.
Dodejme je¹tì, ¾e trochu slo¾itìj¹ím trikem lze tento problém $1.5$-aproximovat
a ¾e v~nìkterých metrických prostorech (tøeba v~euklidovské rovinì) lze v~polynomiálním
èase najít $(1+\varepsilon)$-aproximaci pro libovolné $\varepsilon>0$. Ov¹em èím
men¹í~$\varepsilon$, tím déle algoritmus pobì¾í.

Trojúhelníková nerovnost nicménì byla pro tento algoritmus naprosto nezbytná.
To není náhoda -- hned doká¾eme, ¾e bez tohoto pøedpokladu je libovolná
aproximace stejnì tì¾ká jako pøesné øe¹ení.

\s{Vìta:} Pokud pro~nìjaké reálné~$t\ge 1$ existuje polynomiální
$t$-aproximaèní algoritmus pro~problém obchodního cestujícího
bez~trojúhelníkové nerovnosti, pak je $\P = \NP$.

\proof Uká¾eme, ¾e pomocí takového aproximaèního algoritmu doká¾eme v~polynomiálním
èase zjistit, zda v grafu existuje hamiltonovská kru¾nice, co¾ je \NP-úplný problém.

Dostali jsme graf~$G$, ve~kterém hledáme hamiltonovskou kru¾nici (zkrácenì HK).
Doplníme $G$ na~úplný graf~$G'$. V¹em pùvodním hranám nastavíme délku na~1,
tìm novým na nìjaké dost velké èíslo~$c$. Kolik to bude, urèíme za chvíli.

Graf~$G'$ je úplný, tak¾e v~nìm urèitì nìjaké HK existují. Ty, které se
vyskytují i v~pùvodním grafu~$G$, mají délku pøesnì~$n$. Jakmile ale
pou¾ijeme jedinou hranu, která z~$G$ nepochází, vzroste délka kru¾nice
alespoò na $n-1+c$.

Podle délky nejkrat¹í HK tedy doká¾eme rozpoznat, zda existuje HK v~$G$.
Potøebujeme ov¹em zjistit i pøes zkreslení zpùsobené aproximací. Musí tedy
platit $tn < n-1+c$. To snadno zajistíme volbou hodnoty~$c$ vìt¹í ne¾ $(t-1) n + 1$.

Na¹e konstrukce pøidala polynomiálnì mnoho hran s~polynomiálnì velkým ohodnocením,
tak¾e graf~$G'$ je polynomiálnì velký vzhledem ke~$G$. Rozhodujeme tedy
existenci HK v~polynomiálním èase a $\P=\NP$.
\qed

\s{Poznámka:} Podobnì mù¾eme dokázat, ¾e pokud $\P\ne\NP$, neexistuje pro problém
obchodního cestujícího ani pseudopolynomiální algoritmus. Staèí pùvodním hranám
pøiøadit délku~1 a novým délku~2.

\h{Aproximaèní schéma pro problém batohu}

Ji¾ víme, jak optimalizaèní verzi problému batohu vyøe¹it v~èase $\O(nC)$,
pokud jsou hmotnosti i ceny na~vstupu pøirozená èísla a $C$ je souèet v¹ech cen.
Jak si poradit, pokud je~$C$ obrovské? Kdybychom mìli ¹tìstí a v¹echny
ceny byly násobky nìjakého èísla~$p$, mohli bychom je tímto èíslem
vydìlit. Tak bychom dostali zadání s~men¹ími èísly, jeho¾ øe¹ením by byla
stejná mno¾ina pøedmìtù jako u~zadání pùvodního.

Kdy¾ nám ¹tìstí pøát nebude, mù¾eme pøesto zkusit ceny vydìlit a výsledky
nìjak zaokrouhlit. Optimální øe¹ení nové úlohy pak sice nemusí odpovídat optimálnímu
øe¹ení té pùvodní, ale kdy¾ nastavíme parametry správnì, bude alespoò jeho dobrou aproximací.

\def\cmax{c_{\rm max}}

\s{Základní my¹lenka:}
Oznaèíme $\cmax$ maximum z~cen~$c_i$. Zvolíme nìjaké pøirozené èíslo~$M < \cmax$
a zobrazíme interval cen $[0, \cmax]$ na $\{0, \ldots, M \}$ (tedy ka¾dou cenu znásobíme pomìrem
$M/\cmax$ a zaokrouhlíme).
Jak jsme tím zkreslili výsledek? V¹imnìme si, ¾e efekt je stejný, jako kdybychom jednotlivé
ceny zaokrouhlili na~násobky èísla $\cmax/M$ (prvky z intervalu
$[i\cdot \cmax/M,(i+1)\cdot \cmax/M)$ se zobrazí na stejný prvek). Ka¾dé $c_i$ jsme tím
tedy zmìnili o~nejvý¹e $\cmax/M$, celkovou cenu libovolné podmno¾iny pøedmìtù pak
nejvý¹e o~$n\cdot \cmax/M$. Navíc odstraníme-li ze vstupu
pøedmìty, které se samy nevejdou do~batohu, má optimální øe¹ení pùvodní úlohy cenu $c^* \ge \cmax$,
tak¾e chyba na¹í aproximace nepøesáhne $n\cdot c^*/M$. Má-li tato chyba být shora omezena
$\varepsilon\cdot c^*$, musíme zvolit $M\ge n/\varepsilon$.

Na~této my¹lence \uv{kvantování cen} je zalo¾en následující algoritmus.

\algo{AproximaceBatohu}
\:Odstraníme ze~vstupu v¹echny pøedmìty tì¾¹í ne¾~$H$.
\:Spoèítáme $\cmax=\max_i c_i$ a zvolíme $M=\lceil n/\varepsilon\rceil$.
\:Kvantujeme ceny: Pro $i=1,\ldots,n$ polo¾íme $\hat{c}_i \= \lfloor c_i \cdot M/\cmax \rfloor$.
\:Vyøe¹íme dynamickým programováním problém batohu pro upravené ceny $\hat{c}_1, \ldots, \hat{c}_n$
a pùvodní hmotnosti i kapacitu batohu.
\:Vybereme stejné pøedmìty, jaké pou¾ilo optimální øe¹ení kvantovaného zadání.
\endalgo

\s{Analýza:}
Kroky 1--3 a 5 jistì zvládneme v~èase $\O(n)$. Krok~4 øe¹í problém batohu
se souètem cen $\hat{C}\le nM = \O(n^2/\varepsilon)$, co¾ stihne v~èase $\O(n\hat{C})=\O(n^3/\varepsilon)$.
Zbývá dokázat, ¾e výsledek na¹eho algoritmu má opravdu relativní chybu nejvý¹e~$\varepsilon$.

Oznaème~$P$ mno¾inu pøedmìtù pou¾itých v~optimálním øe¹ení pùvodní úlohy a $c(P)$
cenu tohoto øe¹ení. Podobnì~$Q$ bude mno¾ina pøedmìtù v~optimálním øe¹ení
nakvantované úlohy a $\hat{c}(Q)$ jeho hodnota v~nakvantovaných cenách. Potøebujeme
odhadnout ohodnocení mno¾iny~$Q$ v~pùvodních cenách, tedy $c(Q)$, a~srovnat
ho s~$c(P)$.

Nejprve uká¾eme, jakou cenu má optimální øe¹ení~$P$ pùvodní úlohy
v~nakvantovaných cenách:
$$
\eqalign{
\hat{c}(P) &= \sum_{i\in P} \hat{c}_i =
\sum_{i\in P} \left\lfloor c_i\cdot {M\over \cmax} \right\rfloor \ge
\sum_{i\in P} \left( c_i\cdot {M\over \cmax} - 1 \right) \ge \cr
&\ge
\left(\sum_{i\in P} c_i \cdot {M\over \cmax}\right) - n =
c(P) \cdot {M\over \cmax} - n.
}
$$
Nyní naopak spoèítejme, jak dopadne optimální øe¹ení~$Q$ nakvantovaného problému pøi pøepoètu
na~pùvodní ceny (to je výsledek na¹eho algoritmu):
$$
\eqalign{
c(Q) &= \sum_{i\in Q} c_i \ge
\sum_{i\in Q} \hat{c}_i \cdot {\cmax\over M} =
\left(\sum_i \hat{c}_i\right) \cdot {\cmax\over M} =
\hat{c}(Q) \cdot {\cmax\over M} \ge
\hat{c}(P) \cdot {\cmax\over M}.
}
$$
Poslední nerovnost platí proto, ¾e $\hat{c}(Q)$ je optimální øe¹ení kvantované úlohy,
zatímco $\hat{c}(P)$ je nìjaké dal¹í øe¹ení té¾e úlohy, které nemù¾e být lep¹í.%
\foot{Zde nás zachraòuje, ¾e aèkoliv u~obou úloh le¾í optimum obecnì jinde, obì mají
stejnou mno¾inu {\I pøípustných øe¹ení,} tedy tìch, která se vejdou do batohu. Kdybychom
místo cen kvantovali hmotnosti, nebyla by to pravda a algoritmus by nefungoval.}
Teï u¾ staèí slo¾it obì nerovnosti a dosadit za~$M$:
$$
\eqalign{
c(Q) &\ge \left( { c(P) \cdot M\over \cmax} - n\right) \cdot {\cmax\over M} \ge
c(P) - {n\cdot \cmax\over n / \varepsilon} \ge c(P) - \varepsilon \cmax \ge \cr
&\ge c(P) - \varepsilon c(P) = (1-\varepsilon)\cdot c(P).
}
$$
Na~pøechodu mezi øádky jsme vyu¾ili toho, ¾e ka¾dý pøedmìt se vejde do batohu,
tak¾e optimum musí být alespoò tak cenné jako nejcennìj¹í z~pøedmìtù.

Shròme, co jsme dokázali:

\s{Vìta:}
Existuje algoritmus, který pro ka¾dé $\varepsilon > 0$ nalezne
{\I $(1 - \varepsilon)$-aproximaci} problému batohu s $n$ pøedmìty v èase
$\O(n^3/\varepsilon)$.

Dodejme je¹tì, ¾e algoritmùm, které dovedou pro ka¾dé $\varepsilon > 0$ najít
v~polynomiálním èase $(1-\varepsilon)$-aproximaci optimálního øe¹ení, øíkáme
{\I polynomiální aproximaèní schémata} (PTAS -- Polynomial-Time Approximation Scheme).
V~na¹em pøípadì je dokonce slo¾itost polynomiální i v~závislosti na~$1/\varepsilon$, tak¾e
schéma je {\I plnì polynomiální} (FPTAS -- Fully Polynomial-Time Approximation Scheme).

\exercises

\ex{Popi¹te polynomiální algoritmus pro hledání nejmen¹ího vrcholového pokrytí stromu.
(To je mno¾ina vrcholù, která obsahuje alespoò jeden vrchol z~ka¾dé hrany.)}

\exx{Naleznìte polynomiální algoritmus pro hledání nejmen¹ího vrcholového pokrytí
bipartitního grafu.}

\hint{Vzpomeòte si na sí» z~algoritmu na nejvìt¹í párování. Jak v~ní vypadají øezy?}

\ex{Uka¾te, jak v~polynomiálnì najít nejvìt¹í nezávislou mno¾inu v~intervalovém grafu.}

\exx{Vyøe¹te v~polynomiálním èase 2-SAT, tedy splnitelnost formulí zadaných v~CNF,
jejich¾ klauzule obsahují nejvý¹e 2 literály.}

\hint{Na ka¾dou klauzuli se mù¾eme podívat jako na implikaci.}

\ex{Problém E3,E3-SAT je zesílením 3,3-SATu. Chceme zjistit splnitelnost formule v~CNF, její¾ ka¾dá
klauzule obsahuje právì tøi rùzné promìnné a ka¾dá promìnná se nachází v~právì tøech klauzulích.
Uka¾te, ¾e tento problém lze øe¹it efektivnì z~toho prostého dùvodu, ¾e ka¾dá taková formule je
splnitelná.}

\hint{Pou¾ijte Hallovu vìtu.}

\ex{Pokusíme se øe¹it problém dvou loupe¾níkù hladovým algoritmem. Probíráme
pøedmìty od~nejdra¾¹ího k~nejlevnìj¹ímu a ka¾dý dáme tomu loupe¾níkovi, který
má zrovna ménì. Je nalezené øe¹ení optimální?}

\ex{Problém tøí loupe¾níkù: Je dána mno¾ina pøedmìtù s~cenami, chceme ji rozdìlit na 3
èásti o~stejné cenì. Navrhnìte pseudopolynomiální algoritmus.}

\ex{Problém \alg{MaxCut}: vrcholy zadaného grafu chceme rozdìlit do dvou mno¾in tak,
aby mezi mno¾inami vedlo co nejvíce hran. Jinými slovy chceme nalézt bipartitní podgraf
s~co nejvíce hranami. Rozhodovací verze tohoto problému je \NP-úplná, zkuste jej
v~polynomiálním èase 2-aproximovat.}

\exx{V~problému \alg{MaxE3-SAT} dostaneme formuli v~CNF, její¾ ka¾dá klauzule obsahuje
právì~3 rùzné promìnné, a~chceme nalézt ohodnocení promìnných, pøi nìm¾ je splnìno co nejvíce
klauzulí. Rozhodovací verze je \NP-úplná. Uka¾te, ¾e pøi náhodném ohodnocení promìnných
je splnìno v~prùmìru $7/8$ klauzulí. Z~toho odvoïte deterministickou $7/8$-aproximaci
v~polynomiálním èase.
}

\hint{Linearita støední hodnoty.}

\ex{Hledejme vrcholové pokrytí následujícím hladovým algoritmem. V~ka¾dém kroku
vybereme vrchol nejvy¹¹ího stupnì, pøidáme ho do pokrytí a odstraníme ho z~grafu
i se v¹emi ji¾ pokrytými hranami. Je nalezené pokrytí nejmen¹í? Nebo alespoò $\O(1)$-aproximace
nejmen¹ího?}

\exx{Uva¾ujme následující algoritmus pro nejmen¹í vrcholové pokrytí grafu. Graf projdeme
do hloubky, do výstupu vlo¾íme v¹echny vrcholy vzniklého DFS stromu kromì listù. Doka¾te,
¾e vznikne vrcholové pokrytí a ¾e 2-aproximuje to nejmen¹í.}

\hint{Najdìte v~$G$ párování obsahující alespoò tolik hran, kolik je polovina poètu
vrcholù vráceného pokrytí. Jak velikost párování souvisí s~velikostí nejmen¹ího vrcholového
pokrytí?}

\exx{V~daném orientovaném grafu hledáme acyklický podgraf s~co nejvíce hranami.
Navrhnìte polynomiální 2-aproximaèní algoritmus.}

\hint{Libovolné oèíslování vrcholù rozdìlí hrany na \uv{dopøedné} a \uv{zpìtné}.}

\endexercises

\hints

\bye
