L3.10 Kapitola K3 — Důkaz / teorie (Slot 3) · [MUST] · žebříček důkazů #1 pro 15. 6. · FOTO checkpoint

VYVRCHOLENÍ: Christofides 3/2 [FOTO]

Jedna nová věc Christofidesův algoritmus: místo zdvojení celé kostry opraví liché stupně minimálním perfektním párováním $M$ — a nové lemma $c(E(M)) \le \mathrm{OPT}/2$ srazí faktor z 2 na $\tfrac{3}{2}$.

Vyvrcholení kapitoly a nejpravděpodobnější důkaz písemky 15. 6. — doslova padl 21. 6. 2021 a koluje ve zkouškových souhrnech 2023 i s řešením. Studentský souhrn cituje zadavatele: „Nestaci napsat factor. Je potreba napsat, proc ma takovy factor.“ Dobrá zpráva: z double-tree [L3.9] už máš tři ze čtyř článků důkazu hotové. Dnes se mění jediná věc — jak levně vyrobit sudé stupně — a přibývá jediné nové lemma.

Kde bydlí dvojka — a koho zdvojení vlastně léčí

Připomeň si řetízek double-tree [L3.9]: $2\,\mathrm{OPT} \ge 2\,c(E(T)) = c(E(L)) \ge c(E(H))$. Dvojka bydlí v prostředním článku — platíme celou kostru podruhé, jen abychom dostali sudé stupně pro Eulerovský tah [L3.8c].

Zkus sám: zdvojení „léčí“ liché stupně — ale které vrcholy kostry $T$ tu léčbu doopravdy potřebují? A co víš o jejich počtu?

Jen vrcholy, které mají v $T$ lichý stupeň — vrcholům se sudým stupněm zdvojení „pomáhá“ zbytečně (sudý stupeň ×2 je pořád sudý, ale byl sudý už předtím). Označme množinu lichých vrcholů $W$. A z [L0.2] víš (princip sudosti: $\sum_v \deg(v) = 2|E|$), že vrcholů lichého stupně je v každém grafu sudý počet — $|W|$ je sudé. To není detail, to je klíč k celé dnešní konstrukci.

Zkus sám (návrh konstrukce): máš sudě mnoho „nemocných“ vrcholů $W$ v úplném grafu $K_n$. Jaká nejmenší množina přidaných hran zvedne stupeň každého vrcholu z $W$ přesně o 1 — a nikomu jinému nesáhne na stupeň?

Hrany, které se každého vrcholu z $W$ dotýkají právě jednou a vrcholů mimo $W$ vůbec — to je přesně perfektní párování (perfect matching) na množině $W$ [L0.6]. Existuje, protože $|W|$ je sudé a $K_n$ je úplný (každá dvojice má hranu). Po přidání párování má každý vrchol z $W$ stupeň lichý+1 = sudý a ostatní beze změny → celý multigraf má sudé stupně → Eulerovský tah existuje [L3.8c]. A protože chceme co nejlevnější opravu, vezmeme min-weight perfect matching $M$. Zbytek linky (Euler → shortcutting) zůstává z [L3.9] beze změny.

Přesně to je Christofidesův algoritmus [1976]. Slide 26 (EN 1:1):

Slide 26 — Christofides' Algorithm [1976] (1:1)
Input:  An instance (K_n, c) of metric TSP.
Output: Hamiltonian circuit H.

  1  Find a minimum weight spanning tree T in K_n;
  2  Let W be the set of vertices having an odd degree in T;
  3  Find a minimum weight matching M of nodes from W in K_n;
  4  Merge of T and M forms a multigraph (V(K_n), E(T) ∪ M)
     in which we find the Eulerian walk L;
  5  Transform the Eulerian walk L into the Hamiltonian circuit H
     in the complete graph K_n;

Observation (1:1): „Each edge connects 2 nodes $\Rightarrow$ the sum of the degree of all nodes is $2|E|$ $\Rightarrow$ there are an even number of nodes with an odd degree in every graph (and an arbitrary number of nodes with an even degree). Due to this and completeness of $K_n$, it is possible to find the perfect matching. The merging of $T$ and $M$ ensures even degree of all vertices in the multigraph and thus existence of Eulerian walk.“

Min-weight perfect matching tady bereme jako POJEM — nepanikař

Pro dnešní důkaz potřebuješ od párování jen dvě věci: že na $W$ existuje ($|W|$ sudé + úplnost $K_n$, viz Observation) a že $M$ je ze všech perfektních párování na $W$ nejlevnější. Jak se min-weight perfect matching počítá (přes toky), přijde až v [L4.12] — pro tento důkaz to nepotřebuješ a u zkoušky se to u této úlohy nechce. Definice párování: [L0.6].

Celý běh na známé instanci

Stejná metrická $K_5$, na které běžel double-tree [L3.9] (tabulka cen je v [L3.8a]; $\mathrm{OPT} = 11$ enumerací v [L3.8b]) — ať vidíš oba algoritmy vedle sebe:

Drobnost k poctivosti: tady vyšlo $T \cap M = \emptyset$, takže $T \cup M$ je obyčejný graf. Obecně může $M$ obsahovat i hranu, která už v $T$ je — pak je $T \cup M$ multigraf s dvojitou hranou, Eulerovu tahu to nevadí [L3.8c]. A že na této malé instanci skončily oba algoritmy u stejného okruhu $H$ za 12, není podvod: liší se záruka ($16{,}5$ vs. $22$), ne nutně výstup na jedné konkrétní instanci — faktor je worst-case vlastnost [L3.1].

Nové lemma: $c(E(M)) \le \mathrm{OPT}/2$

Z double-tree důkazu [L3.9] přežívají beze změny článek 1 (shortcutting nezdraží, $c(E(L)) \ge c(E(H))$ [L3.8a]) a článek 2 (dolní mez $\mathrm{OPT} \ge c(E(T))$ [L3.8b]). Místo „zdvojení = ×2“ máme nový článek 4, čisté počítání: $L$ projde každou hranu multigrafu $T \cup M$ právě jednou, takže $c(E(T)) + c(E(M)) = c(E(L))$. Zbývá jediná opravdu nová věc — ocenit párování. Tu si teď odvodíš sám, po krocích.

Zkus sám (krok A): optimální okruh $H^*$ stojí $\mathrm{OPT}$ a navštěvuje všechny vrcholy — tedy i všechny vrcholy $W$. Jak z něj vyrobit levný okruh jen po vrcholech $W$? (Nástroj na to už máš.)

Shortcuttingem [L3.8a]: projdi $H^*$ a vrcholy mimo $W$ přeskakuj — souvislé úseky přes ne-$W$ vrcholy nahraď přímou hranou mezi krajními $W$-vrcholy. Dostaneš okruh $C_W$, který navštíví vrcholy $W$ v pořadí, v jakém leží na $H^*$, a díky (zobecněné) trojúhelníkové nerovnosti nezdraží: $c(C_W) \le c(E(H^*)) = \mathrm{OPT}$. Pozor, zapamatuj si: tohle je druhé místo důkazu, kde se používá metrika (první je článek 1). U double-tree měla metrika jen jednu adresu — u Christofidese má dvě.

Zkus sám (krok B): okruh $C_W$ má $|W|$ hran a $|W|$ je sudé. Jak z jeho hran vyrobit dvě perfektní párování množiny $W$?

Obarvi hrany okruhu střídavě — ber „každou druhou“: liché hrany do $M_1$, sudé do $M_2$. Na okruhu se sudým počtem vrcholů se barvy potkají bez konfliktu a každý vrchol je v každé barvě pokryt právě jednou (má na okruhu 2 hrany, jednu od každé barvy) → $M_1$ i $M_2$ jsou perfektní párování na $W$ a dohromady vyčerpají všechny hrany: $c(E(M_1)) + c(E(M_2)) = c(C_W)$. Přesně to říká slide jednou větou: „the perfect matching $M$ considers every second edge in the alternating path“. (Kdyby byl počet vrcholů lichý, střídání se „kousne“ — proto je sudost $|W|$ [L0.2] nepostradatelná.)

Zkus sám (krok C): dvě párování v součtu stojí $c(C_W) \le \mathrm{OPT}$. Dotáhni odhad pro naše párování $M$ z kroku 3 algoritmu.

Dvě čísla se součtem $\le \mathrm{OPT}$ nemohou být obě větší než $\mathrm{OPT}/2$, takže $\min\{c(E(M_1)), c(E(M_2))\} \le \tfrac{\mathrm{OPT}}{2}$ — slide: „being the minimum weight matching it chooses the smaller half“. A $M$ je nejlevnější perfektní párování na $W$ vůbec, tedy levnější i než levnější z téhle dvojice:

$$c(E(M)) \;\le\; \min\{c(E(M_1)),\, c(E(M_2))\} \;\le\; \frac{c(C_W)}{2} \;\le\; \frac{\mathrm{OPT}(K_n, c)}{2}.$$

Lemma platí pro každou instanci metrického TSP — $H^*$ je důkazový objekt: vždy existuje, algoritmus ho znát nemusí. (Toto rozepsání po krocích A–C je vlastní rozpracování; slide 27 celé lemma konstatuje jedinou větou v bodu 3.)

Totéž na naší instanci, krok po kroku ($H^* = A,D,C,B,E,A$ za 11 — enumerace v [L3.8b]):

Důkaz faktoru 3/2: čtyři články, jeden řetízek

Zkus sám (finále): máš čtyři fakta — (1) $c(E(L)) \ge c(E(H))$, (2) $\mathrm{OPT} \ge c(E(T))$, (3) $\tfrac{\mathrm{OPT}}{2} \ge c(E(M))$, (4) $c(E(M)) + c(E(T)) = c(E(L))$. Sestav řetízek od $\tfrac{3}{2}\,\mathrm{OPT}$ k $c(E(H))$.

Sečti (2) a (3): $\mathrm{OPT} + \tfrac{\mathrm{OPT}}{2} = \tfrac{3}{2}\,\mathrm{OPT} \ge c(E(T)) + c(E(M))$ — nerovnosti se stejným směrem se sčítat smí. Pak (4) přepiš součet na $c(E(L))$ a (1) sestup z tahu na okruh:

$$\frac{3}{2}\, \mathrm{OPT}(K_n, c) \;\stackrel{2.,3.}{\ge}\; c(E(T)) + c(E(M)) \;\stackrel{4.}{=}\; c(E(L)) \;\stackrel{1.}{\ge}\; c(E(H)).$$

Čteno od konce: $c(E(H)) \le \tfrac{3}{2}\,\mathrm{OPT}$ — Christofides je $\tfrac{3}{2}$-aproximace. Srovnej s double-tree: tam řetízek začínal $2\,\mathrm{OPT} \ge 2\,c(E(T))$, tady druhou kostru za $\le \mathrm{OPT}$ nahradilo párování za $\le \tfrac{\mathrm{OPT}}{2}$.

Slide 27 (EN 1:1) říká totéž:

Slide 27 — Christofides' Algorithm is a $\frac{3}{2}$ Approximation (1:1)

Time complexity is $\mathcal{O}(n^3)$. It is a $\frac{3}{2}$ approximation algorithm for the metric TSP:

$$\frac{3}{2} \mathrm{OPT}(K_n, c) \stackrel{2.,3.}{\ge} c(E(T)) + c(E(M)) \stackrel{4.}{=} c(E(L)) \stackrel{1.}{\ge} c(E(H))$$
Zkus sám (inventura předpokladů — u double-tree ses ji učil, teď ji aktualizuj): kde všude důkaz potřebuje trojúhelníkovou nerovnost, kde nezápornost a kde úplnost $K_n$?

Trojúhelníková nerovnost: nově DVĚ adresy — článek 1 (shortcut $L \to H$) a článek 3 (shortcut $H^* \to C_W$ uvnitř lemmatu). Nezápornost: článek 2 (odebraná hrana, $c(e) \ge 0$ [L3.8b]). Úplnost $K_n$: třikrát — zkratky v článku 1, zkratky v článku 3 a existence perfektního párování na $W$ (Observation). Článek 4 je čisté počítání. Bez metriky padají články 1 i 3 najednou — a z [L3.6] víš, že obecný TSP žádnou r-aproximaci nemá, takže to ani jinou fintou opravit nejde.

Složitost a srovnání

Slide 27 uvádí složitost $\mathcal{O}(n^3)$ — dražší než double-tree ($\mathcal{O}(n^2)$), nejdražším krokem je výpočet min-weight perfect matchingu (vlastní komentář, slide jen konstatuje číslo). Odměnou je lepší záruka:

sudé stupně zařídícena opravyfaktorsložitost
Double-tree [L3.9]druhá kopie celé kostry$c(E(T)) \le \mathrm{OPT}$$2$$\mathcal{O}(n^2)$
Christofidespárování lichých vrcholů $W$$c(E(M)) \le \tfrac{\mathrm{OPT}}{2}$$\tfrac{3}{2}$$\mathcal{O}(n^3)$
Pozor: nebezpečné polopravdy
Key takeaways — L3.10
T01 Approximation Factor of Christofides' Algorithm FOTO checkpoint zdroj: zkouška KO 21. 6. 2021 EN 1:1 (oba dochované přepisy shodné; algoritmus = banka #33 / slide 26); řešení dle slidu 27 = dochované vzorové řešení z fotek, rozepsání lemmatu 3 vlastní (přiznáno)
Assignment (EN 1:1)

Derive Approximation Factor of Christofides' Algorithm:

Input: An instance $(K_n, c)$ of metric TSP.

Output: Hamiltonian circuit $H$.

  1. Find a minimum weight spanning tree $T$ in $K_n$;
  2. Let $W$ be the set of vertices having an odd degree in $T$;
  3. Find a minimum weight matching $M$ of nodes from $W$ in $K_n$;
  4. Merge of $T$ and $M$ forms a multigraph $(V(K_n), E(T) \cup M)$ in which we find the Eulerian circuit $L$;
  5. Transform the Eulerian circuit $L$ into the Hamiltonian circuit $H$ in the complete graph $K_n$;

Pozn.: zkouškové znění říká „Eulerian circuit“, slidy „Eulerian walk“ — obojí značí týž uzavřený tah přes všechny hrany [L3.8c].

a) Co je v zadání?

Důkazová úloha č. 1 žebříčku: algoritmus je v zadání darovaný — tvoje práce je odvodit faktor $\tfrac{3}{2}$, tj. vyslovit 4 dílčí tvrzení, každé zdůvodnit (hlavně lemma $c(E(M)) \le \mathrm{OPT}/2$) a složit řetízek. Připomeň si citát zadavatele: nestačí napsat faktor, je potřeba napsat, proč má takový faktor.

b) Co k tomu budeme potřebovat?

c) Jak nad úlohou uvažovat?

Než začneš nerovnosti, věnuj dvě věty přípustnosti: proč $L$ existuje ($|W|$ sudé → párování existuje → $T \cup M$ má sudé stupně a je souvislý) a proč zkratky existují (úplnost). Pak piš čtyři očíslované články; 1, 2 a 4 jsou na jednu větu, lemma 3 rozepiš celé (shortcut $H^*$ na $W$ → dvě párování → levnější polovina → minimalita $M$). Nakonec slož řetízek a zkontroluj směry nerovností: začíná u $\tfrac{3}{2}\mathrm{OPT}$, končí u $c(E(H))$.

d) Úplné řešení (dle slidu 27 / vzorového řešení; lemma 3 rozepsáno)

Přípustnost výstupu. Vrcholů lichého stupně v $T$ je sudý počet ($\sum_v \deg_T(v) = 2|E(T)|$), takže $|W|$ je sudé a díky úplnosti $K_n$ na $W$ existuje perfektní párování — i minimální $M$. V multigrafu $T \cup M$ má každý vrchol z $W$ stupeň o 1 vyšší (sudý) a ostatní beze změny (sudé); graf je souvislý (obsahuje kostru) ⇒ Eulerovský tah $L$ existuje a navštíví všechny vrcholy. Zkratky v kroku 5 existují (úplnost) ⇒ $H$ je Hamiltonovský okruh.

Článek 1 ($c(E(L)) \ge c(E(H))$): shortcutting nahrazuje úseky tahu přímými hranami; podle (zobecněné) trojúhelníkové nerovnosti se cena nezvýší ([L3.8a] T02).

Článek 2 ($\mathrm{OPT}(K_n,c) \ge c(E(T))$): odebráním jedné hrany z optimálního okruhu vznikne kostra; minimalita MST a nezápornost cen dají $c(E(T)) \le \mathrm{OPT} - c(e) \le \mathrm{OPT}$ ([L3.8b] T01).

Článek 3 ($\tfrac{\mathrm{OPT}}{2} \ge c(E(M))$): vezmi optimální okruh $H^*$ a shortcutni ho na vrcholy $W$ (vrcholy mimo $W$ přeskoč) — vznikne okruh $C_W$ po $W$ s $c(C_W) \le \mathrm{OPT}$ (trojúhelníková nerovnost, podruhé v důkazu). Okruh $C_W$ má sudý počet vrcholů, takže jeho hrany „ob jednu“ tvoří dvě perfektní párování $M_1, M_2$ na $W$ s $c(E(M_1)) + c(E(M_2)) = c(C_W)$. Levnější z nich stojí $\le \tfrac{c(C_W)}{2} \le \tfrac{\mathrm{OPT}}{2}$ a $M$ je minimální perfektní párování na $W$, tedy $c(E(M)) \le \min\{c(E(M_1)), c(E(M_2))\} \le \tfrac{\mathrm{OPT}}{2}$. (Slide formuluje jednou větou: matching „considers every second edge in the alternating path“ a jako minimální „chooses the smaller half“.)

Článek 4 ($c(E(M)) + c(E(T)) = c(E(L))$): $L$ projde každou hranu multigrafu $T \cup M$ právě jednou a multigraf obsahuje přesně hrany $T$ a hrany $M$.

Složení.

$$\frac{3}{2}\, \mathrm{OPT}(K_n, c) \;\stackrel{2.,3.}{\ge}\; c(E(T)) + c(E(M)) \;\stackrel{4.}{=}\; c(E(L)) \;\stackrel{1.}{\ge}\; c(E(H)),$$

tedy $c(E(H)) \le \tfrac{3}{2}\,\mathrm{OPT}(K_n,c)$ pro každou instanci metrického TSP — Christofidesův algoritmus je (polynomiální, $\mathcal{O}(n^3)$) $\tfrac{3}{2}$-aproximační algoritmus. $\blacksquare$

FOTO checkpoint

Tohle je důkaz č. 1 pro 15. 6. Napiš ho celý NA PAPÍR zpaměti (bez lekce, bez řešení): algoritmus v 5 krocích, dvě věty o přípustnosti ($|W|$ sudé → párování existuje → sudé stupně → Euler), čtyři očíslované články se zdůvodněním a složený řetízek. Pošli mi fotku — zkontroluju hlavně lemma 3 (shortcut $H^*$ na $W$ → dvě párování → levnější polovina → minimalita $M$), obě místa s trojúhelníkovou nerovností a směry nerovností v řetízku.

T02 The key lemma — where exactly does $c(E(M)) \le \mathrm{OPT}/2$ come from? zdroj: úloha VLASTNÍ (přiznáno) — drill na nejčastější doplňující otázky k bodu 3; instance = metrická K₅ z [L3.8a]
Assignment (own, EN)

Consider Christofides' algorithm on a metric TSP instance $(K_n, c)$ and let $W$ be the set of odd-degree vertices of the minimum spanning tree $T$. (a) Why does a perfect matching of $W$ exist in $K_n$? (b) Prove in detail that the minimum weight perfect matching $M$ of $W$ satisfies $c(E(M)) \le \mathrm{OPT}(K_n,c)/2$. (c) List all places where the proof of the $\tfrac32$ factor uses the triangle inequality; what breaks on a non-metric instance? (d) Illustrate (b) on the 5-city instance from the lesson ($\mathrm{OPT} = 11$, $W = \{B, C, D, E\}$): write down the circuit on $W$ obtained from the optimal circuit, both matchings and their costs.

a) Co je v zadání?

Pitva jediného opravdu nového kroku důkazu. Když u ústní odvyprávíš Christofidese, doplňující otázka skoro jistě míří sem: „proč přesně platí bod 3?“ a „kde všude je metrika?“. Část (d) tě nutí lemma jednou spočítat — nejlepší pojistka proti odříkávání naučené věty.

b) Co k tomu budeme potřebovat?

  • Tato lekce — kroky A–C lemmatu + stepper.
  • [L0.2] — sudý počet vrcholů lichého stupně.
  • [L0.6] — perfektní párování.
  • [L3.8a] — shortcutting a zobecněná trojúhelníková nerovnost.
  • [L3.6] — proč bez metriky nejde zachránit vůbec nic.

c) Jak nad úlohou uvažovat?

U (a) spoj dva fakty: počet lichých vrcholů + úplnost. U (b) drž pořadí kroků A (shortcut $H^*$ na $W$), B (rozpad sudého okruhu na dvě párování), C (levnější polovina + minimalita $M$) — a u každého kroku si řekni, který předpoklad používá. U (d) si nejdřív najdi pořadí vrcholů $W$ podél optimálního okruhu; párování pak vznikají střídáním hran, ne výběrem „nejlevnějších dvojic“.

d) Úplné řešení (vlastní)

(a) Součet stupňů $\sum_v \deg_T(v) = 2|E(T)|$ je sudý, takže vrcholů lichého stupně je sudý počet — $|W|$ je sudé [L0.2]. V úplném grafu lze sudě mnoho vrcholů vždy spárovat (libovolně je rozdvojkuj — každá dvojice má hranu); mezi všemi perfektními párováními existuje minimální $M$.

(b) Nechť $H^*$ je optimální okruh, $c(E(H^*)) = \mathrm{OPT}$. Krok A: projdi $H^*$ a vrcholy mimo $W$ přeskakuj; každý vynechaný úsek nahradí přímá hrana mezi $W$-vrcholy a podle zobecněné trojúhelníkové nerovnosti se nezdraží ⇒ okruh $C_W$ po vrcholech $W$ (v pořadí podél $H^*$) s $c(C_W) \le \mathrm{OPT}$. Krok B: $C_W$ má $|W|$ hran, $|W|$ sudé ⇒ hrany ob jednu tvoří dvě perfektní párování $M_1, M_2$ množiny $W$ a $c(E(M_1)) + c(E(M_2)) = c(C_W)$. Krok C: $\min\{c(E(M_1)), c(E(M_2))\} \le \tfrac{c(C_W)}{2} \le \tfrac{\mathrm{OPT}}{2}$ a z minimality $M$ plyne $c(E(M)) \le \min\{c(E(M_1)), c(E(M_2))\} \le \tfrac{\mathrm{OPT}}{2}$. $\blacksquare$

(c) Dvě místa: článek 1 (shortcut Eulerova tahu $L$ na výstup $H$) a článek 3, krok A (shortcut $H^*$ na $C_W$). Na nemetrické instanci mohou obě zkratky zdražit: o $c(E(H))$ pak neumíme říct nic a lemma $c(E(M)) \le \mathrm{OPT}/2$ také padá. Opravit to nelze — obecný TSP nemá žádnou r-aproximaci, pokud P ≠ NP [L3.6]. (Algoritmus by přesto doběhl a vrátil nějaký Hamiltonovský okruh — přípustnost metriku nepotřebuje, jen záruka ceny.)

(d) $H^* = A,D,C,B,E,A$ s cenou $3+2+1+3+2 = 11$. Jediný ne-$W$ vrchol je $A$; přeskočením úseku $E \to A \to D$ (zkratka $\{E,D\}$: $5 \le 2 + 3 = 5$, zde rovnost) vznikne okruh na $W$ v pořadí podél $H^*$: $C_W = D,C,B,E,D$ s cenou $2+1+3+5 = 11 \le 11 = \mathrm{OPT}$. Střídání hran: $M_1 = \{\{D,C\}, \{B,E\}\}$ za $2+3 = 5$, $M_2 = \{\{C,B\}, \{E,D\}\}$ za $1+5 = 6$; součet $11 = c(C_W)$. Levnější polovina: $5 \le 5{,}5 = \mathrm{OPT}/2$. Minimální párování z běhu algoritmu bylo $M = \{\{B,E\}, \{C,D\}\}$ za 5 — zde náhodou $M = M_1$, obecně může být $M$ ještě levnější než obě $M_i$.

← Předchozí L3.9 · Double-tree algoritmus (2-aproximace metrického TSP)