\input lecnotes.tex
-\prednaska{9}{Aproximaèní algoritmy}{}
+\prednaska{9}{Co si poèít s tì¾kým problémem}{}
-\>Na~minulých pøedná¹kách jsme se zabývali rùznými tì¾kými rozhodovacími
-problémy. Tato se zabývá postupy, jak se v~praxi vypoøádat s~øe¹ením tìchto
-problémù.
+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:
-\h{Co dìlat, kdy¾ potkáme NP-úplný problém}
\algo
-\:Nepanikaøit.
-\:Spokojit se s~málem.
-\:Rozmyslet, jestli opravdu potøebujeme obecný algoritmus. Mnohdy potøebujeme pouze
-speciálnìj¹í pøípady, které mohou být øe¹itelné v~polynomiálním èase.
-\:Spokojit se s~pøibli¾ným øe¹ením, (pou¾ít aproximaèní algoritmus).
-\:Pou¾ít heuristiku -- napøíklad genetické algoritmy nebo randomizované algoritmy.
-Velmi pomoci mù¾e i jen výhodnìj¹í poøadí pøi~prohledávání èi oøezávání nìkterých
-napohled nesmyslných vìtví výpoètu.
+\:{\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
-\h{První zpùsob: Speciální pøípad}
+\>Nyní si nìkteré z~tìchto technik pøedvedeme na konkrétních pøíkladech.
-\>Èasto si vystaèíme s~vyøe¹ením speciálního pøípadu NP-úplného problému, který
-le¾í v~$P$. Napøíklad pøi øe¹ení grafové úlohy nám mù¾e staèit øe¹ení
-pro~speciální druh grafù (stromy, bipartitní grafy, \dots). Barvení grafu je lehké
-napø. pro~dvì barvy èi pro intervalové grafy. 2-SAT, jako speciální pøípad SATu,
-se dá øe¹it v~lineárním èase.
+\h{Nejvìt¹í nezávislá mno¾ina ve stromu}
-\>Uká¾eme si dva takové pøípady (budeme øe¹ení hledat, nejen rozhodovat, zda existuje)
+Uká¾eme, ¾e hledání nejvìt¹í nezávislé mno¾iny je snadné, pokud graf je strom.
-\s{Problém: Maximální nezávislá mno¾ina ve~stromì (ne rozhodovací)}
+\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$.
-\>{\I Vstup:} Zakoøenìný strom~$T$.
+\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
-\>{\I Výstup:} Maximální (co do~poètu vrcholù) nezávislá mno¾ina vrcholù~$M$~v~$T$.
+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í.)
-\>BÚNO mù¾eme pøedpokládat, ¾e v~$M$ jsou v¹echny listy $T$. Pokud by nìkterý
-list $l$ v~$M$ nebyl, tak se podíváme na~jeho otce:
-\itemize\ibull
-\:Pokud otec není v~$M$, tak list $l$ pøidáme do~$M$, èím¾ se nezávislost
-mno¾iny zachovala a velikost stoupla o~1.
-\:Pokud tam otec je, tak ho z~$M$ vyjmeme a na~místo nìho vlo¾íme $l$.
-Nezávislost ani velikost $M$ se nezmìnily.
-\endlist
-\>Nyní listy spolu s~jejich otci z~$T$ odebereme a postup opakujeme. $T$ se
-mù¾e rozpadnout na~les, ale to nevadí $\to$ tentý¾ postup aplikujeme na~v¹echny stromy v~lese.
+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.
-\s{Algoritmus:}
-\>MaxNz$(T)$
\algo
-\:Polo¾íme $L$:=$\{$listy stromu $T\}$.
-\:Polo¾íme $O$:=$\{$otcové vrcholù z~$L\}$.
-\:Vrátíme $L \cup$ MaxNz$(T\setminus(O \cup L))$.
+\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
-\>{\I Poznámka:} Toto doká¾eme naprogramovat v~$\O(n)$ (udr¾ujeme si frontu listù).
-\s{Problém: Batoh}
+\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:
-\>Je daná mno¾ina $n$~pøedmìtù s~hmotnostmi $h_1,\ldots,h_n$
+\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}
+
+Je daná mno¾ina $n$~pøedmìtù s~hmotnostmi $h_1,\ldots,h_n$
a cenami $c_1,\ldots,c_n$ a~batoh, který unese hmostnost~$H$. Najdìte takovou
podmno¾inu pøedmìtù, jejich¾ celková hmotnost je maximálnì $H$ a celková cena
je maximální mo¾ná.
-\>Tento problém je zobecnìním problému batohu z~minulé pøedná¹ky dvìma smìry:
+Tento problém je zobecnìním problému batohu z~minulé pøedná¹ky dvìma smìry:
Jednak místo rozhodovacího problému øe¹íme optimalizaèní, jednak pøedmìty
mají ceny (pøedchozí verze odpovídala tomu, ¾e ceny jsou rovny hmotnostem).
Uká¾eme si algoritmus pro øe¹ení tohoto obecného problému, 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$
+Pou¾ijeme dynamické programování. Pøedstavme si problém omezený na~prvních~$k$
pøedmìtù. Oznaème si $A_k(c)$ (kde $0\le c\le C$) minimální hmotnost
podmno¾iny, její¾ cena je právì~$c$. Tato $A_k$ spoèteme indukcí podle~$k$:
Pro $k=0$ je urèitì $A_0(0)=0$, $A_0(c)=infty$ pro $c>0$. Pokud ji¾ známe
Tímto zpùsobem v~èase $\O(C)$ spoèteme $A_k(c)$ pro fixní $k$ a v¹echna $c$,
v~èase $\O(nC)$ pak v¹echny $A_k(c)$.
-\>Podle $A_n$ snadno nalezneme maximální cenu mno¾iny, která se vejde do~batohu.
+Podle $A_n$ snadno nalezneme maximální cenu mno¾iny, která se vejde do~batohu.
To bude nejvìt¹í~$c^*$, pro nì¾ je $A_n(c^*) \le H$. Jeho nalezení nás stojí
èas $\O(C)$.
-\>A~jak zjistit, které pøedmìty do~nalezené mno¾iny patøí? Upravíme algoritmus,
+A~jak 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.
-\>Ukázali jsme tedy algoritmus s~èasovou slo¾itostí $\O(nC)$, který vyøe¹í
+Ukázali jsme tedy algoritmus s~èasovou slo¾itostí $\O(nC)$, který vyøe¹í
problém batohu. Jeho slo¾itost není polynomem ve~velikosti vstupu ($C$~mù¾e
být a¾ exponenciálnì velké vzhledem k~velikosti vstupu), ale pouze ve~velikosti
èísel na~vstupu. Takovým algoritmùm se øíká {\I pseudopolynomiální.} Ani takové
a ze~$Z_n$ vyèteme výsledek. V¹echny tyto mno¾iny
mají nejvý¹e $H$ prvkù, tak¾e celková èasová slo¾itost algoritmu je~$\O(nH)$.
-\h{Druhý zpùsob: Aproximace}
-
-\>V pøedcházejících problémech jsme se zamìøili na~speciální pøípady. Obèas v¹ak
-takové ¹tìstí nemáme a musíme vyøe¹it celý NP-úplný problém. Mù¾eme si v¹ak
-pomoct tím, ¾e se ho nebudeme sna¾it vyøe¹it optimálnì -- namísto optimálního
-øe¹ení najdeme nìjaké, které je nejvý¹e $c$-krát hor¹í pro nìjakou konstantu $c$.
+\h{Aproximace problému obchodního cestujícího}
\s{Problém: Obchodní cestující}
\>{\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
+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
\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
+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
+
+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
\varepsilon n+1 &< c
}
$$
-\>Kdyby takový algoritmus existoval, máme polynomiální algoritmus
+Kdyby takový algoritmus existoval, máme polynomiální algoritmus
na~hamiltonovskou kru¾nici.
\qed
\s{Základní my¹lenka:}
-Oznaèíme si $c_{max}$ maximum z~cen~$c_i$. Zvolíme si nìjaké pøirozené èíslo~$M < c_{max}$
-a zobrazíme interval cen $[0, c_{max}]$ na $[0,M]$ (tedy ka¾dou cenu znásobíme
-$M/c_{max}$).
+\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 $c_{max}/M$ (prvky z intervalu
-$[i\cdot c_{max}/M,(i+1)\cdot c_{max}/M)$ se zobrazí na stejný prvek). Ka¾dé $c_i$ jsme tím
-tedy zmìnili o~nejvý¹e $c_{max}/M$, celkovou cenu libovolné podmno¾iny pøedmìtù pak
-nejvý¹e o~$n\cdot c_{max}/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 c_{max}$,
-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.}
+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 $c_{max}=\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/c_{max} \rfloor$.
+\: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
-\>Kroky 1--3 a 5 jistì zvládneme v~èase $\O(n)$. Krok~4 øe¹í problém batohu
+\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$.
-Nejprve si rozmyslíme, jakou cenu budou mít pøedmìty které daly optimální øe¹ení
-v pùvodním zadání (tedy mají v pùvodním zadání dohromady cenu $OPT$),
-kdy¾ jejich ceny nakvantujeme (mno¾inu indexù tìchto pøedmìtù si oznaèíme~$Y$):
+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{
-\widehat{OPT} &= \sum_{i\in Y} \hat{c}_i =
-\sum_i \left\lfloor c_i\cdot {M\over c_{max}} \right\rfloor \ge
-\sum_i \left( c_i\cdot {M\over c_{max}} - 1 \right) \ge \cr
+\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 c_{max}}\biggr) - n =
-OPT \cdot {M\over c_{max}} - n.
+\biggl(\sum_i c_i \cdot {M\over \cmax}\biggr) - n =
+c(P) \cdot {M\over \cmax} - n.
}
$$
-Nyní spoèítejme, jak dopadne optimální øe¹ení~$Q$ nakvantovaného problému pøi pøepoètu
+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{
-ALG &= \sum_{i\in Q} c_i \ge
-\sum_i \hat{c}_i \cdot {c_{max}\over M} =
-\biggl(\sum_i \hat{c}_i\biggr) \cdot {c_{max}\over M} \ge^*
-\widehat{OPT} \cdot {c_{max}\over M}.
+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}.
}
$$
-Nerovnost $\ge^*$ platí proto, ¾e $\sum_{i\in Q} \hat{c}_i$ je optimální øe¹ení
-kvantované úlohy, zatímco $\sum_{i\in Y} \hat{c}_i$ je nìjaké dal¹í øe¹ení té¾e úlohy,
-které nemù¾e být lep¹í. Teï u¾ staèí slo¾it obì nerovnosti a dosadit za~$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{
-ALG &\ge \biggl( { OPT \cdot M\over c_{max}} - n\biggr) \cdot {c_{max}\over M} \ge
-OPT - {n\cdot c_{max}\over n / \varepsilon} \ge OPT - \varepsilon c_{max} \ge \cr
-&\ge OPT - \varepsilon OPT = (1-\varepsilon)\cdot OPT.
+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,
projects / ads2.git / blobdiff