Knapsack: fractional greedy + 2-aproximace
Po čtyřech TSP lekcích střih: dnešní důkaz je maximalizační — jediný v kapitole. V [L3.1] jsme definici r-aproximace pro maximalizaci citovali přesně z dnešního slidu 6 a slíbili, že vzor „horní mez $B \ge J^*$ a $J^A \ge B/2$“ uvidíš v akci. Je to krátký důkaz za jisté body: u zkoušky doložen 24. 5. 2011 („2-aproximační algoritmus pro Knapsack“) a v testech z přednášky 2014/2015 chodil v jedné sadě s Bratleym a Christofidesem [L3.10].
Batoh a jeho frakční relaxace
Knapsack problem (problém batohu) znáš modelově: binární rozhodnutí „vzít / nevzít“ [L0.8]. Slide 3 (EN 1:1):
Instance: Nonnegative integers $n, c_1, \ldots, c_n, w_1, \ldots, w_n, W$, where $n$ represents the number of items, $c_1, \ldots, c_n$ represents the cost of each item, $w_1, \ldots, w_n$ represents the weight of each item and $W$ is the maximum weight to be carried in the knapsack.
Goal: Find a subset $S \subseteq \{1, \ldots, n\}$ such that $\sum_{j \in S} w_j \le W$ and $\sum_{j \in S} c_j$ is the maximum.
It is one of the “easiest” NP-hard problems. Sometimes it is called 0/1 Knapsack problem.
„Easiest NP-hard“ není básnická licence: batoh není silně NP-těžký [L3.5] — má pseudopolynomiální DP (propočítáš v [L7.1]) a dokonce aproximační schéma. Dnešní 2-aproximace je nejhrubší a nejrychlejší stupeň té škály.
Zkus sám: představ si, že položky smíš řezat — vzít 80 % položky za 80 % ceny. Kterou položkou je nejvýhodnější začít plnit?
Tou s největším poměrem $c_j/w_j$ — cenou za kilogram. Když se dá řezat, nezáleží na tom, jak se položky „skládají“ do zbylé kapacity (žádné kombinatorické přemýšlení o dírách): každé kilo kapacity prostě obsadíš nejdražším dostupným kilem. Přesně tahle relaxace dělá z NP-těžkého problému snadný.
Formálně povolíme zlomky — z binární proměnné [L0.8] se stane spojitá. Slide 4 (EN 1:1):
While relaxing on the indivisibility of each item, we formulate a new problem:
Instance: stejná jako výše.
Goal: Find the rational numbers $x_1, \ldots, x_j, \ldots, x_n$ such that $0 \le x_j \le 1$ and $\sum_{j=1}^{n} x_j \cdot w_j \le W$ and $\sum_{j=1}^{n} x_j \cdot c_j$ is the maximum.
Since the items can be divided (continuous variable $x_j$), we can solve this problem in polynomial time.
Jednu drobnost si podtrhni hned: každé 0/1 řešení je přípustné i frakčně (jedničky a nuly splňují $0 \le x_j \le 1$). Označíme-li $J^*_F$ optimum frakčního batohu (vlastní značení, slidy ho nepojmenovávají), platí $J^*_F \ge J^*$. Za chvíli z toho bude horní mez.
Dantzig [1957]: greedy podle $c/w$
- if $\sum_{j=1}^{n} w_j > W$ (otherwise it has a trivial solution)
- order and re-index the items by their relative cost: $$\frac{c_1}{w_1} \ge \frac{c_2}{w_2} \ge \ldots \ge \frac{c_n}{w_n}$$
- in the ordered sequence find the first item which does not fit in the knapsack ($h := \min \{ j \in \{1, \ldots, n\} : \sum_{i=1}^{j} w_i > W \}$)
- in order to find the optimal solution, we cut off a part of $h$-th item, so that this part fits in the knapsack:
- $x_j := 1$ for $j = 1, \ldots, h-1$
- $x_h := \frac{W - \sum_{i=1}^{h-1} w_i}{w_h}$
- $x_j := 0$ for $j = h+1, \ldots, n$
- sorting of the items takes $\mathcal{O}(n \log n)$, computing $h$ can be done in $\mathcal{O}(n)$ by simple linear scanning, so this algorithm solves the Fractional Knapsack problem in $\mathcal{O}(n \log n)$
- there is an even faster algorithm ([1] page 440) which can solve this problem in $\mathcal{O}(n)$ by reduction to the Weighted Median problem
Položka $h$ — první, která se celá nevejde — je hlavní postava celé lekce. Zapamatuj si ji.
Zkus sám: proč greedy podle $c/w$ frakční batoh opravdu optimálně vyřeší? (Slidy to konstatují; zkus výměnný argument.)
Vezmi libovolné přípustné frakční řešení $x$, které se od greedy řešení liší. Protože $\sum w_j > W$, můžeme předpokládat, že $x$ využívá celou kapacitu $W$ (doplnění nikdy neuškodí, ceny jsou nezáporné). Pak ale existuje dvojice indexů $i < j$ (tedy $c_i/w_i \ge c_j/w_j$), kde $x_i < 1$ a $x_j > 0$: lepší položka není plná, a přesto vezeme kus horší. Výměna: přesuň malé množství váhy $\varepsilon > 0$ z položky $j$ na položku $i$ — přípustnost se nezmění (celková váha zůstává) a cena se změní o $\varepsilon\,(c_i/w_i - c_j/w_j) \ge 0$, takže se nezhorší. Opakováním výměn převedeš $x$ na greedy tvar (plný prefix + jeden řez + nuly) beze ztráty ceny ⇒ greedy řešení je optimální. (Vlastní rozepsání — slide optimalitu jen konstatuje.)
Celý běh na příkladu ze slidu 6 — $c = (6, 20, 2)$, $w = (2, 10, 8)$, $W = 10$:
Most k 0/1: horní mez $\sum_{i=1}^{h} c_i$
Teď zpátky k nedělitelnému batohu. Z [L3.1] víš, jak se dokazuje faktor u maximalizace: potřebuješ vypočitatelnou horní mez $B \ge J^*$ a pak ukázat $J^A \ge B/r$. Otázka za celou lekci: kde vzít $B$?
Zkus sám: vyrob horní mez celočíselného optima $J^*$ z toho, co už máš — z Dantzigova frakčního řešení. (Dva kroky, oba už znáš.)
Krok 1 (relaxace): každé 0/1 řešení je přípustné i frakčně, takže $J^* \le J^*_F$. Krok 2 (tvar frakčního optima): Dantzig říká přesně, kolik $J^*_F$ je — plný prefix plus kus položky $h$: $J^*_F = \sum_{i=1}^{h-1} c_i + x_h c_h$. A protože $x_h \le 1$, je to nanejvýš $\sum_{i=1}^{h} c_i$. Dohromady:
$$J^* \;\le\; J^*_F \;=\; \sum_{i=1}^{h-1} c_i + x_h c_h \;\le\; \sum_{i=1}^{h} c_i.$$Tohle je mez $B = \sum_{i=1}^{h} c_i$ — spočítáš ji v $\mathcal{O}(n)$, optimum znát nemusíš. Proto jsme se učili frakční batoh: je to stroj na horní mez. Na příkladu: $J^* = 20 \le J^*_F = 22 \le B = 26$.
2-aproximace: lepší z prefixu a $\{h\}$
Mez máme. Zbývá najít přípustné 0/1 řešení, které z ní vytěží aspoň polovinu. První nápad zní: „vezmi všechno, co se vešlo celé“, tedy prefix $\{1, \dots, h-1\}$.
Zkus sám: najdi instanci, kde je samotný prefix $\{1,\dots,h-1\}$ libovolně špatný.
$c = (2, 100)$, $w = (1, 100)$, $W = 100$. Poměry $2 \ge 1$ — seřazeno. Kumulativní váhy $1$, $101 > 100$ ⇒ $h = 2$. Prefix $\{1\}$ má cenu 2, ale $J^* = 100$ (vzít položku 2). Nafouknutím (100 → libovolné $W$) je poměr $J^A/J^*$ libovolně blízko nule — prefix sám není aproximační algoritmus, stejná diagnóza jako u nearest neighbor v [L3.1] T02. Všimni si, kdo za to může: skoro celá hodnota meze $B$ sedí v ceně $c_h$ uříznuté položky.
Zkus sám: tak tedy obráceně — stačí brát vždy samotnou položku $\{h\}$?
Ne. Deset položek s $c_j = 1$, $w_j = 1$, plus jedenáctá s $c_{11} = 2$, $w_{11} = 10$; $W = 10$. Poměry $1 \ge \dots \ge 1 \ge 0{,}2$. Prvních deset váží přesně $10 = W$ (to ještě není „přes“), takže $h = 11$. Kandidát $\{h\}$ má cenu 2, ale prefix $\{1,\dots,10\}$ má cenu $10 = J^*$. Tentokrát hodnota meze sedí v prefixu. Pointa: každý kandidát sám o sobě selhává — ale ceny obou v součtu dají $\sum_{i=1}^{h-1} c_i + c_h = B \ge J^*$. Dvě čísla se součtem $\ge J^*$ nemohou být obě menší než $J^*/2$…
A to je celý algoritmus. Slide 6 (EN 1:1) — definici r-aproximace pro maximalizaci už znáš z [L3.1], slide ji opakuje:
r-approximation algorithm for maximization: Algorithm $A$ for objective function $J$ maximization is called $r$-approximation if there exists a number $r \ge 1$ such that $J^A(I) \ge \frac{1}{r} J^*(I)$ for all instances $I$ of this problem.
Theorem. Let $n, c_1, \ldots, c_n, w_1, \ldots, w_n, W, h$ are nonnegative integers that satisfy:
- $w_j \le W$ pro $j = 1, \ldots, n$
- $\sum_{i=1}^{n} w_i > W$
- $\frac{c_1}{w_1} \ge \frac{c_2}{w_2} \ge \ldots \ge \frac{c_n}{w_n}$
- $h = \min \{ j \in \{1, \ldots, n\} : \sum_{i=1}^{j} w_i > W \}$
Then choosing the better of the two solutions $\{1, \ldots, h-1\}$ or $\{h\}$ is 2-approximation alg. for the Knapsack with the time complexity $\mathcal{O}(n)$.
Example: $c = (6, 20, 2)$, $w = (2, 10, 8)$, $W = 10$.
Zkus sám (finále): slož důkaz faktoru 2 ze dvou věcí, které už máš — meze $B = \sum_{i=1}^{h} c_i \ge J^*$ a pozorování o dvou kandidátech.
Pro libovolná čísla $a, b \ge 0$ platí $\max\{a, b\} \ge \frac{a+b}{2}$ (větší z dvojice je aspoň průměr). Dosaď $a = \sum_{i=1}^{h-1} c_i$ (cena prefixu) a $b = c_h$:
$$J^A(I) \;=\; \max\Big\{ \sum_{i=1}^{h-1} c_i,\; c_h \Big\} \;\ge\; \frac{\sum_{i=1}^{h-1} c_i + c_h}{2} \;=\; \frac{\sum_{i=1}^{h} c_i}{2} \;\ge\; \frac{J^*(I)}{2}.$$To je přesně $J^A \ge \frac{1}{r} J^*$ s $r = 2$ — podle definice z [L3.1] je výběr lepšího z obou kandidátů 2-aproximační algoritmus. Oba kandidáti jsou přípustní: prefix váží $\sum_{i=1}^{h-1} w_i \le W$ (z definice $h$) a $\{h\}$ váží $w_h \le W$ (první předpoklad věty!).
Slide 7 (EN 1:1) říká totéž — všimni si, jak první dvě odrážky „splácejí“ předpoklady věty:
- Given any instance of the Knapsack problem, we can omit all items whose weight is bigger than the knapsack maximum load.
- If $\sum_{i=1}^{n} w_i \le W$ then the whole set of items is an optimal solution.
- Since $\sum_{i=1}^{h} c_i$ is an upper bound on the optimum value, the better of two solutions $\{1, \ldots, h-1\}$ and $\{h\}$ achieves at least half of the optimum value, e.i., $$J^A(I) = \max\Big\{ \sum_{i=1}^{h-1} c_i,\, c_h \Big\} \ge \frac{\sum_{i=1}^{h} c_i}{2} > \frac{1}{2} J^*(I)$$
Drobnost k poctivosti (vlastní komentář): ostrá nerovnost na konci platí, když $c_h > 0$ (pak $J^*_F = \sum_{i=1}^{h-1} c_i + x_h c_h$ je díky $x_h < 1$ ostře pod mezí $B$); pro faktor 2 každopádně stačí neostré $\ge \tfrac12 J^*$. A k složitosti: $\mathcal{O}(n)$ ve větě je za seřazené položky (řazení je v předpokladech) — kompletní postup od syrového vstupu stojí $\mathcal{O}(n \log n)$ za sort, jako Dantzig.
Běh na příkladu ze slidu 6 (pokračování frakčního stepperu):
Zkus sám (inventura předpokladů — kapitolní rituál): k čemu přesně důkaz potřebuje $w_j \le W$, $\sum_i w_i > W$, seřazení podle $c/w$ a nezápornost?
$w_j \le W$: přípustnost kandidáta $\{h\}$ — bez ní by $\max$ porovnával s nepřípustným řešením a celý důkaz padá; proto proof začíná vyhozením těžkých položek (těch se nedotkne ani optimum, vyhodit je smíme). $\sum_i w_i > W$: existence $h$ — jinak se vejde všechno a vracíš celou množinu, což je optimum (druhá odrážka proofu). Seřazení: bez něj „prefix“ a $h$ nic neznamenají — horní mez $B \ge J^*$ stojí na Dantzigově optimalitě, a ta na pořadí podle $c/w$. Nezápornost: ve výměnném argumentu (doplňování kapacity neuškodí) a v $\max\{a,b\} \ge \frac{a+b}{2}$ pro $a, b \ge 0$. Srovnej s TSP důkazy [L3.9]/[L3.10]: tam inventura hlídala metriku, tady hlídá přípustnost kandidátů.
Kam to vede
2-aproximace není u batohu konec, ale začátek: slide 12 ji používá jako krok 1 aproximačního schématu (FPTAS) — její výstup $c(S_1)$ kalibruje zaokrouhlení cen a horní mez DP tabulky, výsledkem je $(1+\epsilon)$-aproximace v $\mathcal{O}(n^2 \cdot \frac{1}{\epsilon})$ pro libovolně malé $\epsilon$. Detaily ve volitelné [L7.2]; samotnou DP tabulku (přesné řešení, pseudopolynomiálně) propočítáš v [L7.1]. Pro 15. 6. je jádro dnešek: mez + dva kandidáti + $\max$.
Pozor: nebezpečné polopravdy- „Greedy podle $c/w$ (ber, dokud se vejde) je dobrý i pro 0/1 batoh.“ NE — bez kandidáta $\{h\}$ je libovolně špatný: $c = (2, 100)$, $w = (1, 100)$, $W = 100$ dá 2 místo 100. Optimalita greedy platí jen pro frakční variantu.
- „$\sum_{i=1}^{h-1} c_i$ je horní mez optima.“ NE — prefix je přípustné řešení, tedy DOLNÍ mez. Horní mez vznikne až přidáním $c_h$: $\sum_{i=1}^{h} c_i \ge J^*_F \ge J^*$ (množina $\{1,\dots,h\}$ sama je nepřípustná!).
- „Faktor 2 platí jen vůči frakčnímu optimu.“ NE — řetízek končí u celočíselného $J^*$: $J^A \ge B/2 \ge J^*/2$; frakční optimum je jen mezistanice při výrobě meze.
- „Předpoklad $w_j \le W$ je kosmetika.“ NE — bez něj nemusí být $\{h\}$ přípustné a věta padá. Proto důkaz začíná vyhozením položek těžších než $W$.
- „Batoh je silně NP-těžký, aproximace je to nejlepší, co jde.“ NE — silně NP-těžký není [L3.5]: má pseudopolynomiální DP [L7.1] a FPTAS [L7.2]. (Kontrast: TSP nemá bez metriky vůbec žádnou r-aproximaci [L3.6].)
Key takeaways — L3.11- Fractional knapsack (slide 4): relaxace nedělitelnosti, $0 \le x_j \le 1$. Dantzig (slide 5): seřaď $\frac{c_1}{w_1} \ge \dots \ge \frac{c_n}{w_n}$, $h = \min\{j : \sum_{i \le j} w_i > W\}$, $x_j = 1$ pro $j < h$, $x_h = \frac{W - \sum_{i<h} w_i}{w_h}$, dál nuly — optimální (výměnný argument), $\mathcal{O}(n \log n)$.
- Horní mez: $J^* \le J^*_F = \sum_{i=1}^{h-1} c_i + x_h c_h \le \sum_{i=1}^{h} c_i = B$ — frakční batoh je stroj na mez $B$ pro maximalizační vzor z [L3.1].
- 2-aproximace (slidy 6–7): vezmi lepší z $\{1,\dots,h-1\}$ a $\{h\}$; $J^A = \max \ge \frac{B}{2} \ge \frac{J^*}{2}$, složitost $\mathcal{O}(n)$. Předpoklady: $w_j \le W$ (přípustnost $\{h\}$), $\sum_i w_i > W$ (existence $h$), seřazené poměry (platnost meze).
- Prefix sám i $\{h\}$ sám jsou libovolně špatné — faktor 2 vyrábí teprve $\max$ (dvě čísla se součtem $\ge J^*$ nemohou být obě pod $J^*/2$).
- Batoh není silně NP-těžký [L3.5]: 2-aproximace → DP [L7.1] → FPTAS [L7.2] (2-aproximace je jeho krok 1).
State the greedy algorithm for the fractional knapsack problem, explain why sorting by $c_j/w_j$ is optimal, and give the time complexity.
a) Co je v zadání?
Tři podúkoly: (1) vyslovit Dantzigův algoritmus (seřazení, $h$, řez), (2) zdůvodnit optimalitu greedy pořadí — to je jediná „důkazová“ část, slidy ji nerozepisují, (3) složitost. Typická ústní opora ke 2-aproximaci: kdo neumí frakční batoh, nemá z čeho vyrobit horní mez.
b) Co k tomu budeme potřebovat?
- Tato lekce — slide 5 (algoritmus) + try s výměnným argumentem.
- [L0.8] Binární proměnná — co přesně relaxujeme.
c) Jak nad úlohou uvažovat?
Algoritmus odvyprávěj přes tři role: seřazení (cena za kilogram), plný prefix, řez položky $h$. U optimality nehledej indukci — hledej výměnu: „kdyby optimum vezlo kus horší položky, zatímco lepší není plná…“. U složitosti rozliš sort a lineární průchod.
d) Úplné řešení (algoritmus dle slidu 5; optimalita vlastní)
Algoritmus. Pokud $\sum_{j=1}^n w_j \le W$, vrať $x_j = 1$ pro všechna $j$ (triviální případ). Jinak seřaď a přeindexuj položky podle relativní ceny $\frac{c_1}{w_1} \ge \frac{c_2}{w_2} \ge \dots \ge \frac{c_n}{w_n}$, najdi první nevejdoucí položku $h := \min\{ j : \sum_{i=1}^{j} w_i > W \}$ a polož $x_j := 1$ pro $j = 1, \dots, h-1$; $x_h := \frac{W - \sum_{i=1}^{h-1} w_i}{w_h}$; $x_j := 0$ pro $j > h$.
Proč je seřazení podle $c_j/w_j$ optimální (výměnný argument, vlastní). Poměr $c_j/w_j$ je cena za jednotku váhy. Vezmi optimální frakční řešení $x^*$; protože $\sum w_j > W$ a ceny jsou nezáporné, lze předpokládat $\sum_j x^*_j w_j = W$. Kdyby $x^*$ nemělo greedy tvar, existují $i < j$ s $x^*_i < 1$ a $x^*_j > 0$. Přesun váhy $\varepsilon > 0$ z $j$ na $i$ zachová přípustnost a změní cenu o $\varepsilon(c_i/w_i - c_j/w_j) \ge 0$ — nezhorší ji. Konečně mnoha výměnami dostaneme greedy řešení se stejnou nebo vyšší cenou ⇒ greedy je optimální. (Intuice: každé kilo kapacity má nést co nejdražší kilo nákladu; řezání to dovolí bez kombinatorických ohledů.)
Složitost. Sort $\mathcal{O}(n \log n)$; nalezení $h$ a dopočet $x$ lineární skenování $\mathcal{O}(n)$ — celkem $\mathcal{O}(n \log n)$. Slide dodává: redukcí na Weighted Median problem to jde i v $\mathcal{O}(n)$ ([1] str. 440).
Ilustrace (instance ze slidu 6): $c = (6,20,2)$, $w = (2,10,8)$, $W = 10$; poměry $3 \ge 2 \ge 0{,}25$, $h = 2$, $x = (1;\, 0{,}8;\, 0)$, $J^*_F = 6 + 0{,}8 \cdot 20 = 22$.
The source theorem assumes nonnegative integers $n, c_1, \ldots, c_n, w_1, \ldots, w_n, W, h$ satisfying
$$w_j \le W \quad j = 1, \ldots, n,$$ $$\sum_{i=1}^{n} w_i > W,$$ $$\frac{c_1}{w_1} \ge \frac{c_2}{w_2} \ge \cdots \ge \frac{c_n}{w_n},$$ $$h = \min \left\{ j \in \{1, \ldots, n\} : \sum_{i=1}^{j} w_i > W \right\}.$$Then choosing the better of the two solutions $\{1, \ldots, h-1\}$ and $\{h\}$ is a 2-approximation algorithm for the knapsack problem with time complexity $\mathcal{O}(n)$.
Study task: Prove the theorem. In particular, show why $\sum_{i=1}^{h} c_i$ is an upper bound on the optimum value and why the better of the two candidate solutions achieves at least half of this upper bound.
a) Co je v zadání?
Hlavní úloha lekce — maximalizační obdoba TSP důkazů: věta je darovaná, tvoje práce je důkaz se dvěma jádry, která zadání výslovně jmenuje: (1) proč je $\sum_{i=1}^{h} c_i$ horní mez $J^*$ (přes frakční relaxaci) a (2) proč lepší z kandidátů dosáhne aspoň poloviny ($\max \ge$ průměr). K tomu patří přípustnost obou kandidátů a role předpokladů.
b) Co k tomu budeme potřebovat?
- Tato lekce — mez $B$, oba protipříklady, finále důkazu.
- [L3.1] Aproximační algoritmus a faktor r — definice pro maximalizaci ($J^A \ge \frac1r J^*$) a vzor „mez $B$“.
- T01 výše — Dantzigova optimalita (na ní stojí horní mez).
c) Jak nad úlohou uvažovat?
Piš ve třech blocích. Blok 0 — předpoklady: proč smíme předpokládat $w_j \le W$ a $\sum w_i > W$ (první dvě odrážky slidu 7: těžké položky vyhoď, jinak vrať vše). Blok 1 — mez: řetízek $J^* \le J^*_F \le \sum_{i=1}^{h} c_i$; nezapomeň říct, odkud znáš $J^*_F$ (Dantzig). Blok 2 — polovina: přípustnost obou kandidátů (tady se použije $w_h \le W$!) a $\max\{a,b\} \ge \frac{a+b}{2}$. Nakonec jedna věta o složitosti.
d) Úplné řešení (dle slidu 7; mez rozepsána)
0) Příprava instance. Položky s $w_j > W$ nemohou být v žádném přípustném řešení (ani v optimu) — vyhodíme je, tím zajistíme první předpoklad. Pokud po vyčištění $\sum_{i=1}^{n} w_i \le W$, je celá množina položek přípustná, a protože ceny jsou nezáporné, je optimální — vrátíme ji a jsme hotovi. Jinak platí $\sum_i w_i > W$, položky seřadíme podle $c_j/w_j$ a index $h$ (první nevejdoucí položka) existuje.
1) $\sum_{i=1}^{h} c_i$ je horní mez optima. Každé přípustné 0/1 řešení je přípustné i pro frakční batoh ($x_j \in \{0,1\}$ splňuje $0 \le x_j \le 1$), takže $J^* \le J^*_F$. Frakční optimum známe přesně z Dantzigova algoritmu (T01): $J^*_F = \sum_{i=1}^{h-1} c_i + x_h c_h$ s $x_h = \frac{W - \sum_{i<h} w_i}{w_h} \in [0, 1)$. Tedy
$$J^* \;\le\; J^*_F \;=\; \sum_{i=1}^{h-1} c_i + x_h c_h \;\le\; \sum_{i=1}^{h-1} c_i + c_h \;=\; \sum_{i=1}^{h} c_i.$$2) Lepší kandidát dosáhne aspoň poloviny meze. Oba kandidáti jsou přípustní: prefix $\{1, \dots, h-1\}$ váží $\sum_{i=1}^{h-1} w_i \le W$ (z definice $h$ jako prvního nevejdoucího indexu) a $\{h\}$ váží $w_h \le W$ (předpoklad věty — proto se těžké položky vyhazovaly). Pro nezáporná čísla platí $\max\{a, b\} \ge \frac{a+b}{2}$, tedy
$$J^A(I) = \max\Big\{ \sum_{i=1}^{h-1} c_i,\; c_h \Big\} \;\ge\; \frac{\sum_{i=1}^{h} c_i}{2} \;\ge\; \frac{1}{2} J^*(I).$$(Slide píše na konci ostrou nerovnost — platí pro $c_h > 0$, kdy $x_h c_h < c_h$; pro faktor stačí $\ge$.) Podle definice r-aproximace pro maximalizaci je algoritmus 2-aproximační.
3) Složitost. Nad seřazenými položkami jeden lineární průchod (nalezení $h$, dva součty, $\max$): $\mathcal{O}(n)$, jak tvrdí věta; od syrového vstupu $\mathcal{O}(n \log n)$ kvůli řazení. $\blacksquare$
Kontrola na příkladu slidu 6: $c=(6,20,2)$, $w=(2,10,8)$, $W=10$: $h=2$, kandidáti $\{1\}$ za 6 a $\{2\}$ za 20 → $J^A = 20$; mez $B = 26$, $20 \ge 13 = B/2$; enumerací $J^* = 20$ — zde dokonce optimum.