MST jako dolní mez (OPT ≥ c(MST))
Druhý ze tří stavebních kamenů aproximací metrického TSP. V [L3.8a] Metrický TSP + trojúhelníková nerovnost + shortcutting jsme se naučili z laciného uzavřeného sledu vyrobit Hamiltonovský okruh, aniž bychom zhoršili cenu. Jenže „nezhoršit cenu sledu“ samo o sobě nic neříká o tom, jak daleko jsme od optima. Dnes si pořídíme měřítko: číslo, které umíme spočítat v polynomiálním čase a které je zaručeně pod $\mathrm{OPT}$.
Problém: jak dokázat faktor vůči číslu, které nikdo nezná?
Cíl příštích lekcí je dokázat záruky typu $c(H) \le 2 \cdot \mathrm{OPT}$ (double-tree [L3.9]) a $c(H) \le \tfrac{3}{2} \cdot \mathrm{OPT}$ (Christofides [L3.10]). Háček: $\mathrm{OPT}$ je řešení silně NP-těžké úlohy [L3.8a] — nikdo ho nezná a důkaz se na jeho hodnotu nesmí odvolávat.
Zkus sám: recept na tenhle problém už máš z [L3.1] Co je aproximační algoritmus a faktor r. Jak se dokazuje $J^A \le r \cdot J^*$ u minimalizace, když $J^*$ neznáme?
Přes vypočitatelnou mez: najdi veličinu $B$, kterou spočítat umíš a o které dokážeš obecně (pro každou instanci) dvě věci — $B \le J^*$ (dolní mez na optimum) a $J^A \le r \cdot B$ (výstup algoritmu je nejvýš $r$-násobek meze). Složením $J^A \le r \cdot B \le r \cdot J^*$, a $J^*$ se v důkazu vůbec nemuselo vyčíslit.
Otázka dneška tedy zní: jaké $B$ vzít pro TSP? Potřebujeme polynomiálně spočitatelný objekt, který je „příbuzný“ Hamiltonovskému okruhu a zaručeně levnější.
Kandidát: minimální kostra
Zkus sám: Hamiltonovský okruh [L3.3] prochází všemi vrcholy. Který levný, polynomiálně spočitatelný objekt z K0 taky „drží všechny vrcholy pohromadě“ — a co s okruhem udělat, aby ses k němu dostal? (Nápověda: okruh má $n$ hran, ten objekt $n-1$.)
Kostra, konkrétně ta nejlevnější — MST [L0.5] Minimální kostra (MST): spojuje všechny vrcholy, má $n-1$ hran a Kruskal/Prim ji najdou hladově v polynomiálním čase. Od okruhu ($n$ hran) ji dělí jediná hrana: odeber z okruhu libovolnou hranu a zbyde souvislý graf na všech $n$ vrcholech s $n-1$ hranami — kostra (dokonce Hamiltonovská cesta). Přesně tohle pozorování jsme si v [L0.5] předplatili „na později“ — a později je teď.
Tvrzení je bod 2 důkazu na slidu 25 (a slovo od slova se opakuje jako bod 2 na slidu 27 u Christofidese):
„while deleting one edge in the circuit, we create the tree. Therefore, inequality $\mathrm{OPT}(K_n, c) \ge c(E(T))$ holds“
Zde $T$ je minimální kostra $K_n$ a $\mathrm{OPT}(K_n,c)$ cena optimálního Hamiltonovského okruhu.
Důkaz krok po kroku
Slide má jednu větu — my si ji rozepíšeme tak, abys ji u zkoušky uměl obhájit do detailu. Vezmi optimální okruh $H^*$ s cenou $c(E(H^*)) = \mathrm{OPT}(K_n,c)$ a odeber z něj libovolnou hranu $e$.
Zkus sám (krok 1): co přesně je $H^* - e$ za objekt? Zdůvodni přes ekvivalence stromu z [L0.4]: počet hran, souvislost, všechny vrcholy.
$H^*$ má $n$ hran (každý vrchol právě jednou opustí) a je souvislý. Po odebrání jedné hrany: souvislost zůstane — zbytek okruhu pořád spojuje oba konce $e$ „druhou stranou dokola“; vrcholů je stále všech $n$; hran je $n-1$. Souvislý graf na $n$ vrcholech s $n-1$ hranami je strom na všech vrcholech, tedy kostra [L0.4]. (Konkrétně je to Hamiltonovská cesta — kostra tvaru „cesta přes všechny vrcholy“.)
Zkus sám (krok 2): teď máš v ruce kostru $H^* - e$. Napiš řetízek nerovností, který z ní vymáčkne $c(E(T)) \le \mathrm{OPT}$. Které dvě nerovnosti potřebuješ a co každou z nich zdůvodňuje?
Dvě nerovnosti, každá s vlastní adresou:
$$c(E(T)) \;\le\; c(E(H^* - e)) \;=\; \mathrm{OPT}(K_n,c) - c(e) \;\le\; \mathrm{OPT}(K_n,c).$$- První: $T$ je minimální kostra a $H^* - e$ je nějaká kostra — minimum nepřebije žádný jiný exemplář [L0.5].
- Druhá: $c(e) \ge 0$ — ceny jsou nezáporné (v metrickém TSP dokonce $c : E(K_n) \to \mathbb{R}^+$ z definice [L3.8a]).
Hotovo: $\mathrm{OPT}(K_n, c) \ge c(E(T))$. $\blacksquare$
Celý důkaz si přehraj na konkrétní instanci — je to tatáž metrická $K_5$ (tabulka cen), na které v [L3.8a] běžel shortcutting:
Co důkaz potřebuje — a co kupodivu ne
Zkus sám: projdi důkaz znovu a hledej, kde se použila trojúhelníková nerovnost. Najdeš ji?
Nikde. Důkaz použil jen: okruh minus hrana = kostra (čistá teorie grafů), minimalitu MST a nezápornost cen. Nerovnost $\mathrm{OPT} \ge c(\mathrm{MST})$ tedy platí pro každý TSP s nezápornými cenami, i nemetrický. Metrika (a úplnost $K_n$) je potřeba až v jiném kroku důkazů — shortcuttingu [L3.8a], který z laciného sledu vyrábí okruh. Dolní mez sama je „zadarmo navíc“.
Pozor na jemnost: nezápornost vypustit nejde — se zápornou hranou $e$ by $c(E(H^*)) - c(e) > \mathrm{OPT}$ a druhá nerovnost řetízku padá.
Zkus sám: mez funguje i „z druhé strany“. Vezmi okruh $H = A,B,C,D,E,A$ s cenou 12, který v [L3.8a] vypadl ze shortcuttingu. Co o $\mathrm{OPT}$ téhle instance víš, když $c(\mathrm{MST}) = 7$?
Sendvič: každý přípustný okruh dává horní mez ($\mathrm{OPT}$ je minimum, takže $\mathrm{OPT} \le 12$), MST dává dolní mez ($\mathrm{OPT} \ge 7$). Tedy $7 \le \mathrm{OPT} \le 12$ — aniž bychom optimum počítali. (Skutečné $\mathrm{OPT} = 11$, viz stepper; obě meze sedí.) Přesně takhle se dolní mez používá i prakticky: certifikuje, jak daleko nejvýš od optima tvé řešení může být.
K čemu to bude: bod 2 obou velkých důkazů
Dnešní nerovnost je jediné místo, kudy do důkazů faktorů vstupuje neznámé $\mathrm{OPT}$. Řetízek double-tree (slide 25, 1:1):
$$2\, \mathrm{OPT}(K_n, c) \stackrel{2.}{\ge} 2\, c(E(T)) \stackrel{3.}{=} c(E(L)) \stackrel{1.}{\ge} c(E(H))$$Bod 1 (shortcutting) máš z [L3.8a], bod 2 je dnešní dolní mez, bod 3 (Eulerovský tah $L$ nad zdvojenou kostrou stojí $2\,c(E(T))$) přijde v [L3.8c] — a v [L3.9] už jen řetízek slepíme. Christofides [L3.10] použije bod 2 ve stejném znění (slide 27) a místo zdvojení přidá ke kostře levné párování. V obou případech: algoritmus si postaví levný sled z MST, důkaz ho přes dnešní mez sváže s $\mathrm{OPT}$.
Pozor: nebezpečné polopravdy- „MST je (skoro) řešení TSP.“ NE — kostra není okruh, není to přípustné řešení TSP. $c(\mathrm{MST})$ je jen číslo-měřítko; okruh z kostry teprve musíš vyrobit (zdvojení [L3.8c] + shortcutting [L3.8a]) a při tom se cena až zdvojnásobí.
- Směr nerovnosti: $\mathrm{OPT} \ge c(\mathrm{MST})$, nikdy naopak. Mnemotechnika: okruh = kostra + jedna hrana navíc, takže okruh je „víc než“ kostra; a optimální okruh je pořád aspoň MST, protože MST je úplně nejlevnější způsob, jak vrcholy spojit.
- „Tahle mez potřebuje trojúhelníkovou nerovnost.“ NE — stačí nezáporné ceny; platí i pro nemetrický TSP. Metrika je potřeba v jiných krocích (shortcutting). Naopak nezápornost vypustit nejde ($c(e) \ge 0$ drží druhou nerovnost řetízku).
- „Dolní mez = hotová aproximace.“ NE — mez sama žádný okruh nevyrábí. Faktor vznikne až spárováním s konstrukcí: okruh s cenou $\le 2\,c(\mathrm{MST})$ [L3.9], resp. $\le \tfrac{3}{2}$-násobkem [L3.10].
Key takeaways — L3.8b- $\mathrm{OPT}(K_n,c) \ge c(E(T))$ (slide 25 bod 2 = slide 27 bod 2): odeber z optimálního okruhu jednu hranu → vznikne kostra (Hamiltonovská cesta) [L0.4]; řetízek $c(\mathrm{MST}) \le c(E(H^*)) - c(e) \le \mathrm{OPT}$ [L0.5].
- Důkaz potřebuje jen nezáporné ceny — trojúhelníkovou nerovnost NE; mez platí pro každý TSP. Metrika je potřeba až u shortcuttingu [L3.8a].
- Role dle receptu z [L3.1]: $B = c(\mathrm{MST})$ je polynomiálně vypočitatelná dolní mez na neznámé $\mathrm{OPT}$ — centrální mez pro double-tree [L3.9] i Christofidese [L3.10].
- Sendvič: libovolný přípustný okruh dává horní mez, MST dolní — $c(\mathrm{MST}) \le \mathrm{OPT} \le c(\text{okruh})$ bez znalosti optima.
- MST není přípustné řešení TSP — je to měřítko; okruh z něj teprve vyrobí [L3.8c] + shortcutting.
Step 2 of the proof that the double-tree algorithm is a 2-approximation states: „while deleting one edge in the circuit, we create the tree. Therefore, inequality $\mathrm{OPT}(K_n, c) \ge c(E(T))$ holds“, where $T$ is a minimum weight spanning tree of $K_n$.
Study questions (own): (i) Prove the inequality in detail. (ii) Point out exactly where the proof uses that the edge costs are non-negative. (iii) Does the proof use the triangle inequality? What does this tell you about the validity of the bound for non-metric TSP instances?
a) Co je v zadání?
Důkazová mini-úloha: rozepsat jednu větu slidu 25 do plného argumentu a vyjasnit si, které předpoklady krok skutečně spotřebuje. U zkoušky je to bod 2 důkazů faktorů 2 i 3/2 — nestačí ho odcitovat, chtějí slyšet proč.
b) Co k tomu budeme potřebovat?
- Tato lekce — rozklad na dvě nerovnosti a jejich adresy.
- [L0.4] Strom, kostra, les, DAG — souvislý graf s $n-1$ hranami je strom.
- [L0.5] Minimální kostra (MST) — MST je nejlevnější ze všech koster (a T02 tam tenhle krok trénuje poprvé).
- [L3.8a] — definice metrického TSP ($c : E(K_n) \to \mathbb{R}^+$).
c) Jak nad úlohou uvažovat?
(i) Začni u optimálního okruhu $H^*$ — jediného objektu, o kterém něco víš (má $n$ hran, je souvislý, jeho cena JE $\mathrm{OPT}$). Odeber hranu, pojmenuj, co zbylo, a srovnej to s MST. (ii) Projdi řetízek nerovností a u každé se ptej „co ji drží?“. (iii) Udělej inventuru použitých předpokladů — je mezi nimi trojúhelníková nerovnost?
d) Úplné řešení (vlastní rozepsání jednořádkového argumentu slidu 25)
(i) Nechť $H^*$ je optimální Hamiltonovský okruh, $c(E(H^*)) = \mathrm{OPT}(K_n, c)$, a $e \in E(H^*)$ libovolná jeho hrana. Podgraf $H^* - e$: obsahuje všech $n$ vrcholů, je souvislý (oba konce $e$ spojuje zbytek okruhu) a má $n - 1$ hran — podle ekvivalencí z [L0.4] je to strom na všech vrcholech, tedy kostra (konkrétně Hamiltonovská cesta). Protože $T$ je minimální kostra a $H^* - e$ je nějaká kostra:
$$c(E(T)) \;\le\; c(E(H^* - e)) \;=\; \mathrm{OPT}(K_n, c) - c(e) \;\le\; \mathrm{OPT}(K_n, c). \qquad \blacksquare$$(ii) Nezápornost drží poslední nerovnost: $\mathrm{OPT} - c(e) \le \mathrm{OPT}$ platí právě díky $c(e) \ge 0$. V metrickém TSP ji garantuje definice $c : E(K_n) \to \mathbb{R}^+$ [L3.8a]. (První nerovnost je čistá minimalita MST, žádné předpoklady o cenách nepotřebuje.)
(iii) Ne — trojúhelníková nerovnost se v důkazu nikde nepoužila. Mez $\mathrm{OPT} \ge c(\mathrm{MST})$ proto platí pro každou TSP instanci s nezápornými cenami, i nemetrickou. Metrika je v důkazech faktorů potřeba jinde: v bodu 1 (shortcutting, [L3.8a]), který z Eulerovského tahu vyrábí okruh bez zdražení. To je také důvod, proč samotná dolní mez nestačí k aproximaci nemetrického TSP — mez platí, ale levný okruh z kostry už bez metriky vyrobit neumíme (a podle [L3.6] ani žádná jiná cesta nevede, pokud $P \ne NP$).
Consider the metric TSP instance on nodes $\{A, B, C, D, E\}$ from lesson [L3.8a] with costs $c(A,B){=}2$, $c(A,C){=}3$, $c(A,D){=}3$, $c(A,E){=}2$, $c(B,C){=}1$, $c(B,D){=}2$, $c(B,E){=}3$, $c(C,D){=}2$, $c(C,E){=}4$, $c(D,E){=}5$.
(a) Compute a minimum spanning tree $T$ and its cost $c(E(T))$ using Kruskal's algorithm. (b) The shortcutting in [L3.8a] produced the Hamiltonian circuit $H = A,B,C,D,E,A$ of cost 12. Using $T$ and $H$, derive the best bounds on $\mathrm{OPT}(K_5, c)$ you can — without enumerating tours. (c) Verify that the (not yet proven) double-tree promise $c(H) \le 2 \cdot \mathrm{OPT}$ is consistent with your bounds.
a) Co je v zadání?
Početní procvičení dnešní meze: spočítat MST Kruskalem, sevřít neznámé $\mathrm{OPT}$ do sendviče mezi dolní mez (MST) a horní mez (libovolný přípustný okruh) a zkontrolovat konzistenci s budoucím faktorem 2.
b) Co k tomu budeme potřebovat?
- Tato lekce — $\mathrm{OPT} \ge c(\mathrm{MST})$ a sendvič.
- [L0.5] Minimální kostra (MST) — Kruskalův běh na papíře.
- [L3.8a] T02 — odkud se vzal okruh $H$ a jeho cena 12.
c) Jak nad úlohou uvažovat?
(a) Seřaď deset hran podle ceny a ber od nejlevnější; hrany uzavírající kružnici zahazuj; skonči u $n-1 = 4$ hran. (b) Jakou nerovnost dává přípustnost okruhu $H$ a jakou dnešní věta? (c) Dosaď do $c(H) \le 2 \cdot \mathrm{OPT}$ nejhorší (nejmenší) přípustnou hodnotu $\mathrm{OPT}$ ze svého sendviče.
d) Úplné řešení (vlastní)
(a) Kruskal. Pořadí hran: $BC(1)$; pak čtyři hrany ceny 2 — $AB, AE, BD, CD$ (pořadí remíz libovolné); pak $AC, AD, BE$ (3); $CE$ (4); $DE$ (5). Běh: $BC$ ✓; $AB$ ✓ (spojí $A$ s $B,C$); $AE$ ✓ (připojí $E$); $BD$ ✓ (připojí $D$) — máme 4 hrany, hotovo. $T = \{BC, AB, AE, BD\}$, $c(E(T)) = 1 + 2 + 2 + 2 = \mathbf{7}$. (Při jiném pořadí remíz může vyjít $CD$ místo $BD$ — jiná MST, ale cena je vždy 7 [L0.5].)
(b) Sendvič. Dolní mez (dnešní věta): $\mathrm{OPT} \ge c(E(T)) = 7$. Horní mez: $H$ je přípustný Hamiltonovský okruh a $\mathrm{OPT}$ je minimum přes všechny okruhy, takže $\mathrm{OPT} \le c(H) = 12$. Celkem
$$7 \;\le\; \mathrm{OPT}(K_5, c) \;\le\; 12.$$(Pro kontrolu — enumerace všech 12 okruhů, kterou úloha nechtěla, dává $\mathrm{OPT} = 11$ pro okruh $A,D,C,B,E,A$; obě meze sedí.)
(c) Konzistence s faktorem 2. Slib double-tree zní $c(H) \le 2 \cdot \mathrm{OPT}$. Nejhorší případ v sendviči je $\mathrm{OPT} = 7$: pak $2 \cdot \mathrm{OPT} = 14 \ge 12 = c(H)$ ✓. Dokonce platí $c(H) = 12 \le 14 = 2 \cdot c(E(T)) \le 2 \cdot \mathrm{OPT}$ — okruh vyrobený přes kostru a shortcutting se do dvojnásobku dolní meze vešel. To není náhoda: přesně tenhle řetízek v [L3.9] dokážeme obecně (chybí už jen bod 3, cena Eulerovského tahu $c(E(L)) = 2\,c(E(T))$, z [L3.8c]).