9-apx/9-apx.tex

   1 \input lecnotes.tex
   2 \prednaska{9}{Co si poèít s tì¾kým problémem}{}
   3
   4 V~pøedchozí kapitole jsme zjistili, ¾e leckteré rozhodovací problémy
   5 jsou \NP-úplné. Z~toho plyne, ¾e jsou ekvivalentní, ale bohu¾el také,
   6 ¾e ani jeden z~nich zatím neumíme vyøe¹it v~polynomiálním èase.
   7
   8 Èasto se stane, ¾e problém, který v~¾ivotì potkáme, patøí mezi \NP-úplné.
   9 Pøesnìji øeèeno spí¹ ne¾ s~rozhodovacím problémem se potkáme s~problémem
  10 {\I optimalizaèním,} ve~kterém jde o~nalezení {\I nejlep¹ího} objektu
  11 s~danou vlastností. To mù¾e být tøeba nejvìt¹í nezávislá mno¾ina v~grafu
  12 nebo obarvení grafu nejmen¹ím mo¾ným poètem barev. Kdybychom umìli efektivnì
  13 øe¹it optimalizaèní problém, umíme samozøejmì øe¹it i pøíslu¹ný rozhodovací,
  14 tak¾e pokud $\P\ne\NP$, jsou i optimalizaèní problémy tì¾ké.
  15
  16 Ale co naplat, svìt nám takové úlohy pøedkládá a my je potøebujeme vyøe¹it.
  17 Na¹tìstí situace není zase tak beznadìjná. Nabízejí se tyto mo¾nosti, co si
  18 poèít:
  19
  20 \algo
  21 \:{\I Spokojit se s~málem.} Nejsou vstupy, pro které problém potøebujeme
  22   øe¹it, dostateènì malé, abychom si mohli dovolit pou¾ít algoritmus
  23   s~exponenciální slo¾itostí? Zvlá¹» kdy¾ takový algoritmus vylep¹íme
  24   proøezáváním neperspektivních vìtví výpoètu a tøeba ho i paralelizujeme.
  25 \:{\I Vyøe¹it speciální pøípad.} Nemají na¹e vstupy nìjaký speciální
  26   tvar, kterého bychom mohli vyu¾ít? Grafové problémy jsou èasto v~\P{}
  27   tøeba pro stromy nebo i obecnìji pro bipartitní grafy. U~èíselných
  28   problémù zase nìkdy pomù¾e, jsou-li èísla na vstupu dostateènì malá.
  29 \:{\I Øe¹ení aproximovat.} Opravdu potøebujeme optimální øe¹ení? Nestaèilo
  30   by nám o~kousíèek hor¹í? Èasto existuje polynomiální algoritmus, který
  31   nalezne nejhùøe $c$-krát hor¹í øe¹ení ne¾ je optimum, kde $c$~je konstanta.
  32 \:{\I Pou¾ít heuristiku.} Neumíme-li nic lep¹ího, mù¾eme sáhnout po~nìkteré
  33   z~mnoha heuristických technik, které sice nic nezaruèují, ale obvykle
  34   nìjaké uspokojivé øe¹ení najdou. Mù¾e pomoci tøeba hladový algoritmus
  35   nebo genetické algoritmy. Èasto platí, ¾e èím déle heuristiku necháme
  36   bì¾et, tím lep¹í øe¹ení najde.
  37 \:{\I Kombinace pøístupù.} Mnohdy lze pøedchozí pøístupy kombinovat:
  38   napøíklad pou¾ít aproximaèní algoritmus a poté jeho výsledek
  39   je¹tì heuristicky vylep¹ovat. Tak získáme øe¹ení, které zaruèenì není
  40   moc daleko od optima, a~pokud budeme mít ¹tìstí, bude k~nìmu velmi blízko.
  41 \endalgo
  42
  43 \>Nyní si nìkteré z~tìchto technik pøedvedeme na konkrétních pøíkladech.
  44
  45 \h{Nejvìt¹í nezávislá mno¾ina ve stromu}
  46
  47 Uká¾eme, ¾e hledání nejvìt¹í nezávislé mno¾iny je pro stromy velmi snadné.
  48
  49 \s{Lemma:} Buï~$T$ zakoøenìný strom a $\ell$ jeho libovolný list. Pak alespoò jedna
  50 z~nejvìt¹ích nezávislých mno¾in obsahuje~$\ell$.
  51
  52 \proof
  53 Mìjme nejvìt¹í nezávislou mno¾inu~$M$, která list~$\ell$ neobsahuje. Podívejme
  54 se na otce~$p$ listu~$\ell$ (kdyby neexistoval, je celý strom jednovrcholový
  55 a tvrzení triviální). Le¾í~$p$ v~$M$? Pokud ne, mohli bychom do~$M$ pøidat
  56 list~$\ell$ a dostali bychom vìt¹í nezávislou mno¾inu. V~opaèném pøípadì z~$M$
  57 odebereme otce~$p$ a nahradíme ho listem~$\ell$, èím¾ dostaneme stejnì velkou
  58 nezávislou mno¾inu obsahující~$\ell$.
  59 \qed
  60
  61 Algoritmus bude pøímoèaøe pou¾ívat toto lemma. Dostane na vstupu strom,
  62 ten zakoøení a zvolí libovolný list. Tento list umístí do nezávislé mno¾iny
  63 a jeho otce odebere, proto¾e se nemù¾e v~nezávislé mno¾inì vyskytovat.
  64 Toto bude opakovat, dokud nìjaké vrcholy zbývají. (Graf se v~prùbìhu mù¾e
  65 rozpadnout na více komponent, ale to nevadí.)
  66
  67 Tento algoritmus jistì pracuje v~polynomiálním èase. ©ikovnou implementací
  68 mù¾eme slo¾itost sní¾it a¾ na lineární. Napøíklad tak, ¾e budeme udr¾ovat seznam
  69 listù. My si uká¾eme jinou lineární implementaci zalo¾enou na prohledávání do hloubky.
  70 Bude pracovat s~polem znaèek~$M$, v~nìm¾ na poèátku bude v¹ude \<false> a postupnì
  71 obdr¾í \<true> v¹echny prvky hledané nezávislé mno¾iny.
  72
  73 \algo
  74 \algin Strom~$T$ s~koøenem~$v$, pole znaèek~$M$.
  75 \:$M[v] \= \<true>$.
  76 \:Pokud je~$v$ list, skonèíme.
  77 \:Pro v¹echny syny~$w$ vrcholu~$v$:
  78 \::Zavoláme se rekurzivnì na podstrom s~koøenem~$w$.
  79 \::Pokud $M[w]=\<true>$, polo¾íme $M[v] \= \<false>$.
  80 \endalgo
  81
  82 \h{Barvení intervalového grafu}
  83
  84 FIXME
  85
  86 \h{Problém batohu s~malými èísly}
  87
  88 \>Je daná mno¾ina $n$~pøedmìtù s~hmotnostmi $h_1,\ldots,h_n$
  89 a cenami $c_1,\ldots,c_n$ a~batoh, který unese hmostnost~$H$. Najdìte takovou
  90 podmno¾inu pøedmìtù, jejich¾ celková hmotnost je maximálnì $H$ a celková cena
  91 je maximální mo¾ná.
  92
  93 \>Tento problém je zobecnìním problému batohu z~minulé pøedná¹ky dvìma smìry:
  94 Jednak místo rozhodovacího problému øe¹íme optimalizaèní, jednak pøedmìty
  95 mají ceny (pøedchozí verze odpovídala tomu, ¾e ceny jsou rovny hmotnostem).
  96 Uká¾eme si algoritmus pro øe¹ení tohoto obecného problému, jeho¾ èasová
  97 slo¾itost bude polynomiální v~poètu pøedmìtù~$n$ a souètu v¹ech cen~$C=\sum_i
  98 c_i$.
  99
 100 \>Pou¾ijeme dynamické programování. Pøedstavme si problém omezený na~prvních~$k$
 101 pøedmìtù. Oznaème si $A_k(c)$ (kde $0\le c\le C$) minimální hmotnost
 102 podmno¾iny, její¾ cena je právì~$c$. Tato $A_k$ spoèteme indukcí podle~$k$:
 103 Pro $k=0$ je urèitì $A_0(0)=0$, $A_0(c)=infty$ pro $c>0$. Pokud ji¾ známe
 104 $A_{k-1}$, spoèítáme $A_k$ následovnì: $A_k(c)$ odpovídá nìjaké podmno¾inì
 105 pøedmìtù z~$1,\ldots,k$. V~této podmno¾inì jsme buïto $k$-tý pøedmìt nepou¾ili
 106 (a pak je $A_k(c)=A_{k-1}(c)$), nebo pou¾ili a tehdy bude $A_k(c) =
 107 A_{k-1}(c-c_k) + h_k$ (to samozøejmì jen pokud $c\ge c_k$). Z~tìchto dvou
 108 mo¾ností si vybereme tu, která dává mno¾inu s~men¹í hmotností. Tedy:
 109 $$
 110 A_k(c) = \min (A_{k-1}(c), A_{k-1}(c-c_k) + h_k).
 111 $$
 112 Tímto zpùsobem v~èase $\O(C)$ spoèteme $A_k(c)$ pro fixní $k$ a v¹echna $c$,
 113 v~èase $\O(nC)$ pak v¹echny $A_k(c)$.
 114
 115 \>Podle $A_n$ snadno nalezneme maximální cenu mno¾iny, která se vejde do~batohu.
 116 To bude nejvìt¹í~$c^*$, pro nì¾ je $A_n(c^*) \le H$. Jeho nalezení nás stojí
 117 èas $\O(C)$.
 118
 119 \>A~jak zjistit, které pøedmìty do~nalezené mno¾iny patøí? Upravíme algoritmus,
 120 aby si pro ka¾dé $A_k(c)$ pamatoval $B_k(c)$, co¾ bude index posledního pøedmìtu,
 121 který jsme do~pøíslu¹né mno¾iny pøidali. Pro nalezené $c^*$ tedy bude $i=B_n(c^*)$
 122 poslední pøedmìt v~nalezené mno¾inì, $i'=B_{i-1}(c^*-c_i)$ ten pøedposlední
 123 a tak dále. Takto v~èase $\O(n)$ rekonstruujeme celou mno¾inu od~posledního
 124 prvku k~prvnímu.
 125
 126 \>Ukázali jsme tedy algoritmus s~èasovou slo¾itostí $\O(nC)$, který vyøe¹í
 127 problém batohu. Jeho slo¾itost není polynomem ve~velikosti vstupu ($C$~mù¾e
 128 být a¾ exponenciálnì velké vzhledem k~velikosti vstupu), ale pouze ve~velikosti
 129 èísel na~vstupu. Takovým algoritmùm se øíká {\I pseudopolynomiální.} Ani takové
 130 algoritmy ale nejsou k dispozici pro v¹echny problémy (napø. u problému obchodního
 131 cestujícího nám vùbec nepomù¾e, ¾e váhy hran budou malá èísla).
 132
 133 \s{Verze bez cen:} Na verzi s~cenami rovnými hmotnostem se dá pou¾ít
 134 i jiný algoritmus zalo¾ený na~dynamickém programování: poèítáme mno¾iny
 135 $Z_k$ obsahující v¹echny hmotnosti men¹í ne¾~$H$, kterých nabývá
 136 nìjaká podmno¾ina prvních~$k$ prvkù. Pøitom $Z_0=\{0\}$, $Z_k$
 137 spoèteme ze~$Z_{k-1}$ --- udr¾ujme si $Z_{k-1}$ jako setøídìný spojový seznam,
 138 výpoèet dal¹ího seznamu udìláme slitím dvou seznamù $Z_{k-1}$ a $Z_{k-1}$ se
 139 v¹emi prvky zvý¹enými o hmotnost $k$ zahazujíce duplicitní a pøíli¹ velké hodnoty ---
 140 a ze~$Z_n$ vyèteme výsledek. V¹echny tyto mno¾iny
 141 mají nejvý¹e $H$ prvkù, tak¾e celková èasová slo¾itost algoritmu je~$\O(nH)$.
 142
 143 \h{Aproximace problému obchodního cestujícího}
 144
 145 \s{Problém: Obchodní cestující}
 146
 147 \>{\I Vstup:} Neorientovaný graf~$G$, ka¾dá hrana
 148 je ohodnocená funkcí $w: E(G)\rightarrow {\bb R }^+_0$.
 149
 150 \>{\I Výstup:} Hamiltonovská kru¾nice (obsahující v¹echny vrcholy grafu), a~to ta nejkrat¹í
 151 (podle ohodnocení).
 152
 153 \>Tento problém je hned na~první pohled nároèný -- u¾ sama existence
 154 hamiltonovské kru¾nice je NP-úplná. Najdeme aproximaèní algoritmus nejprve za pøedpokladu,
 155 ¾e vrcholy splòují trojúhelníkovou nerovnost (tj. $\forall x,y,z \in V: w(xz)\le
 156 w(xy)+w(yz)$), potom uká¾eme, ¾e v úplnì obecném pøípadé by samotná existence
 157 aproximaèního algoritmu implikovala ${\rm P=NP }$.
 158
 159 \>{\I a) trojúhelníková nerovnost:}
 160
 161 Existuje pìkný algoritmus, který najde hamiltonovskou kru¾nici o délce $\leq
 162 2\cdot opt$, kde $opt$ je délka nejkrat¹í hamiltonovské kru¾nice.
 163 Vedle pøedpokladu trojúhelníkové
 164 nerovnosti budeme potøebovat, aby ná¹ graf byl úplný. Souhrnnì mù¾eme
 165 pøedpokládat, ¾e úlohu øe¹íme v nìjakém metrickém protoru, ve kterém jsou obì
 166 podmínky podle definice splnìny.
 167
 168 Najdeme nejmen¹í kostru grafu a obchodnímu cestujícímu poradíme, a» jde po~ní -- kostru
 169 zakoøeníme a projdeme jako strom do hloubky, pøièem¾ se zastavíme a¾ v koøeni po projití
 170 v¹ech vrcholù. Problém v¹ak je, ¾e prùchod po kostøe obsahuje
 171 nìkteré vrcholy i hrany vícekrát, a proto musíme nahradit nepovolené vracení se.
 172 Máme-li na nìjaký vrchol vstoupit podruhé, prostì ho ignorujeme a pøesuneme se
 173 rovnou na dal¹í nenav¹tívený -- dovolit si to mù¾eme, graf je úplný a obsahuje
 174 hrany mezi v¹emi dvojicemi vrcholù
 175 (jinak øeèeno, poøadí vrcholù kru¾nice bude preorder výpis prùchodem do hloubky).
 176 Pokud platí trojúhelníková nerovnost, tak si tìmito zkratkami neu¹kodíme.
 177 Nech» minimální kostra má váhu~$T$. Pokud bychom pro¹li celou kostru, bude mít
 178 sled váhu~$2T$ (ka¾dou hranou kostry jsme ¹li tam a zpátky), a pøeskakování
 179 vrcholù celkovou váhu nezvìt¹uje (pøi pøeskoku
 180 nahradíme cestu $xyz$ jedinou hranou $xz$, pøièem¾ z trojúhelníkové nerovnosti
 181 máme $xz \leq xy + xz$), tak¾e váha nalezené
 182 hamiltonovské kru¾nice bude také nanejvý¹ $2T$.
 183
 184 Kdy¾ máme hamiltonovskou kru¾nici $C$ a z~ní vy¹krtneme hranu, dostaneme kostru
 185 grafu~$G$ s~váhou men¹í ne¾ $C$ -- ale ka¾dá kostra je alespoò tak tì¾ká
 186 jako minimální kostra $T$. Tedy optimální hamiltonovská kru¾nice je urèitì tì¾¹í
 187 ne¾ minimální kostra $T$. Kdy¾ tyto dvì nerovnosti slo¾íme
 188 dohromady, algoritmus nám vrátí hamiltonovskou kru¾nici $T'$ s~váhou nanejvý¹
 189 dvojnásobnou vzhledem k optimální hamiltonovské kru¾nici ($T' \leq 2T < 2C$). Takovéto
 190 algoritmy se nazývají {\I 2-aproximaèní}, kdy¾ øe¹ení je maximálnì dvojnásobné
 191 od~optimálního.\foot{Hezkým trikem se v obecných metrických prostorech umí
 192 $1{,}5$-aproximace. Ve~nìkterých metrických prostorech (tøeba v euklidovské
 193 rovinì) se aproximaèní pomìr dá dokonce srazit na
 194 libovolnì blízko k 1. Zaplatíme ale na èase -- èím pøesnìj¹í výsledek
 195 po algoritmu chceme, tím déle to bude trvat.}
 196
 197 \>{\I b) bez~trojúhelníkové nerovnosti:}
 198
 199 Zde se budeme naopak sna¾it ukázat, ¾e ¾ádný polynomiální aproximaèní
 200 algoritmus neexistuje.
 201
 202 \s{Vìta:} Pokud pro~libovolné~$\varepsilon>0$ existuje polynomiální
 203 $(1+\varepsilon)$-aproximaèní algoritmus pro~problém obchodního cestujícího bez~trojúhelníkové nerovnosti, tak ${\rm P = NP }$.
 204
 205 \proof Uká¾eme, ¾e v~takovém pøípadì doká¾eme v~polynomiálním èase zjistit,
 206 zda v grafu existuje hamiltonovská kru¾nice.
 207
 208 \>Dostali jsme graf~$G$, ve~kterém hledáme hamiltonovskou kru¾nici. Doplníme
 209 $G$ na~úplný graf~$G'$ a~váhy hran~$G'$ nastavíme takto:
 210 \itemize\ibull
 211 \: $w(e) = 1$, kdy¾ $e \in E(G)$
 212 \: $w(e) = c \gg 1$, kdy¾ $e \not\in E(G)$
 213 \endlist
 214 \>Konstantu $c$ potøebujeme zvolit tak velkou, abychom jasnì poznali, jestli
 215 je ka¾dá hrana z nalezené hamiltonovské kru¾nice hranou grafu $G$ (pokud by
 216 nebyla, bude kru¾nice obsahovat aspoò jednu hranu s váhou $c$, která vy¾ene
 217 souèet poznatelnì vysoko). Pokud existuje hamiltonovská kru¾nice v~$G'$ slo¾ená jen
 218 z~hran, které byly
 219 pùvodnì v~$G$, pak optimální øe¹ení bude mít váhu~$n$, jinak bude urèitì
 220 minimálnì $n-1+c$. Kdy¾ máme aproximaèní algoritmus s~pomìrem~$1+\varepsilon$,
 221 musí tedy být
 222 $$
 223 \eqalign{
 224 (1+\varepsilon)\cdot n &< n-1+c \cr
 225 \varepsilon n+1 &< c
 226 }
 227 $$
 228 \>Kdyby takový algoritmus existoval, máme polynomiální algoritmus
 229 na~hamiltonovskou kru¾nici.
 230 \qed
 231
 232 \s{Poznámka:} O existenci pseudopolynomiálního algoritmu
 233 platí analogická vìta, a doká¾e se analogicky -- existující hrany budou
 234 mít váhu 1, neexistující váhu 2.
 235
 236 \h{Aproximaèní schéma pro problém batohu}
 237
 238 Ji¾ víme, jak optimalizaèní verzi problému batohu vyøe¹it v~èase $\O(nC)$,
 239 pokud jsou hmotnosti i ceny na~vstupu pøirozená èísla a $C$ je souèet v¹ech cen.
 240 Jak si poradit, pokud je~$C$ obrovské? Kdybychom mìli ¹tìstí a v¹echny
 241 ceny byly dìlitelné nìjakým èíslem~$p$, mohli bychom je tímto èíslem
 242 vydìlit. Tím bychom dostali zadání s~men¹ími èísly, jeho¾ øe¹ením by byla
 243 stejná mno¾ina pøedmìtù jako u~zadání pùvodního.
 244
 245 Kdy¾ nám ¹tìstí pøát nebude, mù¾eme pøesto zkusit ceny vydìlit a výsledky
 246 nìjak zaokrouhlit. Øe¹ení nové úlohy pak sice nebude pøesnì odpovídat optimálnímu
 247 øe¹ení té pùvodní, ale kdy¾ nastavíme parametry správnì, bude alespoò jeho dobrou aproximací.
 248
 249 \s{Základní my¹lenka:}
 250
 251 \def\cmax{c_{\rm max}}
 252
 253 Oznaèíme si $\cmax$ maximum z~cen~$c_i$. Zvolíme si nìjaké pøirozené èíslo~$M < \cmax$
 254 a zobrazíme interval cen $[0, \cmax]$ na $[0,M]$ (tedy ka¾dou cenu znásobíme
 255 $M/\cmax$).
 256 Jak jsme tím zkreslili výsledek? V¹imnìme si, ¾e efekt je stejný, jako kdybychom jednotlivé
 257 ceny zaokrouhlili na~násobky èísla $\cmax/M$ (prvky z intervalu
 258 $[i\cdot \cmax/M,(i+1)\cdot \cmax/M)$ se zobrazí na stejný prvek). Ka¾dé $c_i$ jsme tím
 259 tedy zmìnili o~nejvý¹e $\cmax/M$, celkovou cenu libovolné podmno¾iny pøedmìtù pak
 260 nejvý¹e o~$n\cdot \cmax/M$. Teï si je¹tì v¹imnìme, ¾e pokud ze~zadání odstraníme
 261 pøedmìty, které se samy nevejdou do~batohu, má optimální øe¹ení pùvodní úlohy cenu $\<OPT>\ge \cmax$,
 262 tak¾e chyba v~souètu je nejvý¹e $n\cdot \<OPT>/M$. Má-li tato chyba být shora omezena
 263 $\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.}
 264
 265 \s{Algoritmus:}
 266 \algo
 267 \:Odstraníme ze~vstupu v¹echny pøedmìty tì¾¹í ne¾~$H$.
 268 \:Spoèítáme $\cmax=\max_i c_i$ a zvolíme $M=\lceil n/\varepsilon\rceil$.
 269 \:Kvantujeme ceny: $\forall i: \hat{c}_i \leftarrow \lfloor c_i \cdot M/\cmax \rfloor$.
 270 \:Vyøe¹íme dynamickým programováním problém batohu pro upravené ceny $\hat{c}_1, \ldots, \hat{c}_n$
 271 a pùvodní hmotnosti i kapacitu batohu.
 272 \:Vybereme stejné pøedmìty, jaké pou¾ilo optimální øe¹ení kvantovaného zadání.
 273 \endalgo
 274
 275 \s{Analýza:}
 276 Kroky 1--3 a 5 jistì zvládneme v~èase $\O(n)$. Krok~4 øe¹í problém batohu
 277 se souètem cen $\hat{C}\le nM = \O(n^2/\varepsilon)$, co¾ stihne v~èase $\O(n\hat{C})=\O(n^3/\varepsilon)$.
 278 Zbývá dokázat, ¾e výsledek na¹eho algoritmu má opravdu relativní chybu nejvý¹e~$\varepsilon$.
 279
 280 Nech» pùvodní úloha má nìjaké optimální øe¹ení~$P$ s~cenou $c(P)$. Rozmysleme
 281 si, jakou cenu $\hat{c}(P)$ bude tato mno¾ina pøedmìtù mít v~nakvantovaném zadání:
 282 $$
 283 \eqalign{
 284 \hat{c}(P) &= \sum_{i\in P} \hat{c}_i =
 285 \sum_i \left\lfloor c_i\cdot {M\over \cmax} \right\rfloor \ge
 286 \sum_i \left( c_i\cdot {M\over \cmax} - 1 \right) \ge \cr
 287 &\ge
 288 \biggl(\sum_i c_i \cdot {M\over \cmax}\biggr) - n =
 289 c(P) \cdot {M\over \cmax} - n.
 290 }
 291 $$
 292 Nyní naopak spoèítejme, jak dopadne optimální øe¹ení~$Q$ nakvantovaného problému pøi pøepoètu
 293 na~pùvodní ceny (to je výsledek na¹eho algoritmu):
 294 $$
 295 \eqalign{
 296 c(Q) &= \sum_{i\in Q} c_i \ge
 297 \sum_i \hat{c}_i \cdot {\cmax\over M} =
 298 \biggl(\sum_i \hat{c}_i\biggr) \cdot {\cmax\over M} \ge
 299 \hat{c}(P) \cdot {\cmax\over M}.
 300 }
 301 $$
 302 Poslední nerovnost platí proto, ¾e $\sum_{i\in Q} \hat{c}_i$ je optimální øe¹ení
 303 kvantované úlohy, zatímco $\sum_{i\in P} \hat{c}_i$ je nìjaké dal¹í øe¹ení té¾e úlohy,
 304 které nemù¾e být lep¹í.%
 305 \foot{Zde nás zachraòuje, ¾e aèkoliv u~obou úloh le¾í optimum obecnì jinde, obì mají
 306 stejnou mno¾inu {\I pøípustných øe¹ení,} tedy tìch, která se vejdou do batohu. Kdybychom
 307 místo cen kvantovali hmotnosti, nebyla by to pravda a algoritmus by nefungoval.}
 308 Teï u¾ staèí slo¾it obì nerovnosti a dosadit za~$M$:
 309 $$
 310 \eqalign{
 311 c(Q) &\ge \biggl( { c(P) \cdot M\over \cmax} - n\biggr) \cdot {\cmax\over M} \ge
 312 c(P) - {n\cdot \cmax\over n / \varepsilon} \ge c(P) - \varepsilon \cmax \ge \cr
 313 &\ge c(P) - \varepsilon c(P) = (1-\varepsilon)\cdot c(P).
 314 }
 315 $$
 316 Algoritmus tedy v¾dy vydá øe¹ení, které je nejvý¹e $(1-\varepsilon)$-krát hor¹í ne¾ optimum,
 317 a~doká¾e to pro libovolné~$\varepsilon$ v~èase polynomiálním v~$n$. Takovému algoritmu øíkáme
 318 {\I polynomiální aproximaèní schéma} (jinak té¾ PTAS\foot{Polynomial-Time Approximation Scheme}).
 319 V~na¹em pøípadì je dokonce slo¾itost polynomiální i v~závislosti na~$1/\varepsilon$, tak¾e
 320 schéma je {\I plnì polynomiální} (øeèené té¾ FPTAS\foot{Fully Polynomial-Time Approximation
 321 Scheme}). U nìkterých problémù se stává, ¾e aproximaèní schéma závisí na
 322 $1/\varepsilon$ exponenciálnì, co¾ tak pøíjemné není. Shròme, co jsme zjistili, do následující vìty:
 323
 324 \s{Vìta:}
 325 Existuje algoritmus, který pro ka¾dé $\varepsilon > 0$ nalezne
 326 {\I $(1 - \varepsilon)$-aproximaci} problému batohu s $n$ pøedmìty v èase
 327 $\O(n^3/\varepsilon)$.
 328
 329 \bye