APX: Batoh

[ads2.git] / 9-apx / 9-apx.tex

\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:

\algo
\:{\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é zaruèenì není
  moc daleko od optima, a~pokud budeme mít ¹tìstí, bude k~nìmu velmi blízko.
\endalgo

\>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
\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
\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 vzroste. 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 problém batohu. Jeho optimalizaèní verze vypadá takto:
Je daná 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(c)=\infty$ pro $c>0$. 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)$, pro v¹echna~$k$ pak $\O(Cn)$.

Jakmile spoèteme~$A_n$, známe pro ka¾dou cenu nejlehèí podmno¾inu s~touto cenou.
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 $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~velikosti 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) nikoliv.

\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$, pøièem¾ hodnoty
vìt¹í ne¾~$H$ zahodíme. 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}

\s{Problém: Obchodní cestující}

\>{\I Vstup:} Neorientovaný graf~$G$, ka¾dá hrana
je ohodnocená funkcí $w: E(G)\rightarrow {\bb R }^+_0$.

\>{\I Výstup:} Hamiltonovská kru¾nice (obsahující v¹echny vrcholy grafu), a~to ta nejkrat¹í
(podle ohodnocení).

Tento problém je hned na~první pohled nároèný -- u¾ sama existence
hamiltonovské kru¾nice je NP-úplná. Najdeme aproximaèní algoritmus nejprve za pøedpokladu,
¾e vrcholy splòují trojúhelníkovou nerovnost (tj. $\forall x,y,z \in V: w(xz)\le
w(xy)+w(yz)$), potom uká¾eme, ¾e v úplnì obecném pøípadé by samotná existence
aproximaèního algoritmu implikovala ${\rm P=NP }$.

\>{\I a) trojúhelníková nerovnost:}

Existuje pìkný algoritmus, který najde hamiltonovskou kru¾nici o délce $\leq
2\cdot opt$, kde $opt$ je délka nejkrat¹í hamiltonovské kru¾nice.
Vedle pøedpokladu trojúhelníkové
nerovnosti budeme potøebovat, aby ná¹ graf byl úplný. Souhrnnì mù¾eme
pøedpokládat, ¾e úlohu øe¹íme v nìjakém metrickém protoru, ve kterém jsou obì
podmínky podle definice splnìny.

Najdeme nejmen¹í kostru grafu a obchodnímu cestujícímu poradíme, a» jde po~ní -- kostru
zakoøeníme a projdeme jako strom do hloubky, pøièem¾ se zastavíme a¾ v koøeni po projití
v¹ech vrcholù. Problém v¹ak je, ¾e prùchod po kostøe obsahuje
nìkteré vrcholy i hrany vícekrát, a proto musíme nahradit nepovolené vracení se.
Máme-li na nìjaký vrchol vstoupit podruhé, prostì ho ignorujeme a pøesuneme se
rovnou na dal¹í nenav¹tívený -- dovolit si to mù¾eme, graf je úplný a obsahuje
hrany mezi v¹emi dvojicemi vrcholù
(jinak øeèeno, poøadí vrcholù kru¾nice bude preorder výpis prùchodem do hloubky).
Pokud platí trojúhelníková nerovnost, tak si tìmito zkratkami neu¹kodíme.
Nech» minimální kostra má váhu~$T$. Pokud bychom pro¹li celou kostru, bude mít
sled váhu~$2T$ (ka¾dou hranou kostry jsme ¹li tam a zpátky), a pøeskakování
vrcholù celkovou váhu nezvìt¹uje (pøi pøeskoku
nahradíme cestu $xyz$ jedinou hranou $xz$, pøièem¾ z trojúhelníkové nerovnosti
máme $xz \leq xy + xz$), tak¾e váha nalezené
hamiltonovské kru¾nice bude také nanejvý¹ $2T$.

Kdy¾ máme hamiltonovskou kru¾nici $C$ a z~ní vy¹krtneme hranu, dostaneme kostru
grafu~$G$ s~váhou men¹í ne¾ $C$ -- ale ka¾dá kostra je alespoò tak tì¾ká
jako minimální kostra $T$. Tedy optimální hamiltonovská kru¾nice je urèitì tì¾¹í
ne¾ minimální kostra $T$. Kdy¾ tyto dvì nerovnosti slo¾íme
dohromady, algoritmus nám vrátí hamiltonovskou kru¾nici $T'$ s~váhou nanejvý¹
dvojnásobnou vzhledem k optimální hamiltonovské kru¾nici ($T' \leq 2T < 2C$). Takovéto
algoritmy se nazývají {\I 2-aproximaèní}, kdy¾ øe¹ení je maximálnì dvojnásobné
od~optimálního.\foot{Hezkým trikem se v obecných metrických prostorech umí
$1{,}5$-aproximace. Ve~nìkterých metrických prostorech (tøeba v euklidovské
rovinì) se aproximaèní pomìr dá dokonce srazit na
libovolnì blízko k 1. Zaplatíme ale na èase -- èím pøesnìj¹í výsledek
po algoritmu chceme, tím déle to bude trvat.}

\>{\I b) bez~trojúhelníkové nerovnosti:}

Zde se budeme naopak sna¾it ukázat, ¾e ¾ádný polynomiální aproximaèní
algoritmus neexistuje.

\s{Vìta:} Pokud pro~libovolné~$\varepsilon>0$ existuje polynomiální
$(1+\varepsilon)$-aproximaèní algoritmus pro~problém obchodního cestujícího bez~trojúhelníkové nerovnosti, tak ${\rm P = NP }$.

\proof Uká¾eme, ¾e v~takovém pøípadì doká¾eme v~polynomiálním èase zjistit,
zda v grafu existuje hamiltonovská kru¾nice.

Dostali jsme graf~$G$, ve~kterém hledáme hamiltonovskou kru¾nici. Doplníme
$G$ na~úplný graf~$G'$ a~váhy hran~$G'$ nastavíme takto:
\itemize\ibull
\: $w(e) = 1$, kdy¾ $e \in E(G)$
\: $w(e) = c \gg 1$, kdy¾ $e \not\in E(G)$
\endlist

Konstantu $c$ potøebujeme zvolit tak velkou, abychom jasnì poznali, jestli
je ka¾dá hrana z nalezené hamiltonovské kru¾nice hranou grafu $G$ (pokud by
nebyla, bude kru¾nice obsahovat aspoò jednu hranu s váhou $c$, která vy¾ene
souèet poznatelnì vysoko). Pokud existuje hamiltonovská kru¾nice v~$G'$ slo¾ená jen
z~hran, které byly
pùvodnì v~$G$, pak optimální øe¹ení bude mít váhu~$n$, jinak bude urèitì
minimálnì $n-1+c$. Kdy¾ máme aproximaèní algoritmus s~pomìrem~$1+\varepsilon$,
musí tedy být
$$
\eqalign{
(1+\varepsilon)\cdot n &< n-1+c \cr
\varepsilon n+1 &< c
}
$$
Kdyby takový algoritmus existoval, máme polynomiální algoritmus
na~hamiltonovskou kru¾nici.
\qed

\s{Poznámka:} O existenci pseudopolynomiálního algoritmu
platí analogická vìta, a doká¾e se analogicky -- existující hrany budou
mít váhu 1, neexistující váhu 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 dìlitelné nìjakým èíslem~$p$, mohli bychom je tímto èíslem
vydìlit. Tím 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. Øe¹ení nové úlohy pak sice nebude pøesnì odpovídat optimálnímu
øe¹ení té pùvodní, ale kdy¾ nastavíme parametry správnì, bude alespoò jeho dobrou aproximací.

\s{Základní my¹lenka:}

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

Oznaèíme si $\cmax$ maximum z~cen~$c_i$. Zvolíme si nìjaké pøirozené èíslo~$M < \cmax$
a zobrazíme interval cen $[0, \cmax]$ na $[0,M]$ (tedy ka¾dou cenu znásobíme
$M/\cmax$).
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$. Teï si je¹tì v¹imnìme, ¾e pokud ze~zadání odstraníme
pøedmìty, které se samy nevejdou do~batohu, má optimální øe¹ení pùvodní úlohy cenu $\<OPT>\ge \cmax$,
tak¾e chyba v~souètu je nejvý¹e $n\cdot \<OPT>/M$. Má-li tato chyba být shora omezena
$\varepsilon\cdot \<OPT>$, musíme zvolit $M\ge n/\varepsilon$.\foot{Pøipomìòme, ¾e toto je¹tì není dùkaz, nebo» velkoryse pøehlí¾íme chyby dané zaokrouhlováním. Dùkaz provedeme ní¾e.}

\s{Algoritmus:}
\algo
\: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: $\forall i: \hat{c}_i \leftarrow \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$.

Nech» pùvodní úloha má nìjaké optimální øe¹ení~$P$ s~cenou $c(P)$. Rozmysleme
si, jakou cenu $\hat{c}(P)$ bude tato mno¾ina pøedmìtù mít v~nakvantovaném zadání:
$$
\eqalign{
\hat{c}(P) &= \sum_{i\in P} \hat{c}_i =
\sum_i \left\lfloor c_i\cdot {M\over \cmax} \right\rfloor \ge
\sum_i \left( c_i\cdot {M\over \cmax} - 1 \right) \ge \cr
&\ge
\biggl(\sum_i c_i \cdot {M\over \cmax}\biggr) - 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 \hat{c}_i \cdot {\cmax\over M} =
\biggl(\sum_i \hat{c}_i\biggr) \cdot {\cmax\over M} \ge
\hat{c}(P) \cdot {\cmax\over M}.
}
$$
Poslední nerovnost platí proto, ¾e $\sum_{i\in Q} \hat{c}_i$ je optimální øe¹ení
kvantované úlohy, zatímco $\sum_{i\in P} \hat{c}_i$ 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 \biggl( { c(P) \cdot M\over \cmax} - n\biggr) \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).
}
$$
Algoritmus tedy v¾dy vydá øe¹ení, které je nejvý¹e $(1-\varepsilon)$-krát hor¹í ne¾ optimum,
a~doká¾e to pro libovolné~$\varepsilon$ v~èase polynomiálním v~$n$. Takovému algoritmu øíkáme
{\I polynomiální aproximaèní schéma} (jinak té¾ PTAS\foot{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í} (øeèené té¾ FPTAS\foot{Fully Polynomial-Time Approximation
Scheme}). U nìkterých problémù se stává, ¾e aproximaèní schéma závisí na
$1/\varepsilon$ exponenciálnì, co¾ tak pøíjemné není. Shròme, co jsme zjistili, do následující vìty:

\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)$.

\bye