Aproximační algoritmy

[zapotocnylubos]

1. Motivace a aproximační poměr

Základ pro vše ostatní – bez tohoto nelze analyzovat žádný algoritmus.

• Proč chceme aproximaci – rychlost vs optimalita
• Aproximační poměr ρ(n) – formální definice
• Jak číst důkaz aproximačního poměru
• 🔢 Příklad: jednoduchý příklad na obarvení grafu – intuice poměru

2. Greedy aproximace

První techniika – přímočará, ale překvapivě silná. Stavební kámen pro Set Cover.

• Greedy jako aproximační strategie
• Kdy greedy funguje dobře a proč
• 🔢 Příklad: Load Balancing – rozdělení úloh na stroje, důkaz poměru 2

3. Vertex Cover

Klasický příklad s jednoduchým a elegantním důkazem – ideální pro pochopení techniky důkazů.

• Definice problému
• Algoritmus – matching-based 2-aproximace
• Důkaz aproximačního poměru 2
• Proč nejde jednoduše dělat lépe (UGC hypotéza)
• 🔢 Příklad: konkrétní graf, krok za krokem

4. Set Cover

Přirozené rozšíření Vertex Cover – složitější důkaz s logaritmickým poměrem.

• Definice problému – zobecnění Vertex Cover
• Greedy algoritmus
• Důkaz aproximačního poměru ln(n)
• Proč je logaritmický poměr v jistém smyslu optimální
• 🔢 Příklad: pokrytí množiny prvků, krok za krokem

5. TSP aproximace

Kombinuje více technik – vyžaduje znalost předchozích sekcí.

• Metrické TSP – proč potřebujeme trojúhelníkovou nerovnost
• 2-aproximace pomocí MST
• Christofides algoritmus – aproximační poměr 1.5
• Proč obecné TSP nelze aproximovat (důkaz)
• 🔢 Příklad: konkrétní graf, porovnání MST přístupu a Christofidese

6. Knapsack FPTAS

Zcela jiná technika – škálování a zaokrouhlování. Ukazuje že někdy lze dostat libovolně přesné řešení.

• Připomenutí exaktního Knapsack DP
• Problém s velkými hodnotami – proč DP nestačí
• Technika škálování hodnot
• Důkaz aproximačního poměru (1 + ε)
• Časová složitost v závislosti na ε
• 🔢 Příklad: konkrétní instance, výpočet pro různé hodnoty ε

7. PTAS a FPTAS

Teoretické zastřešení – přichází na konec, až studenti znají konkrétní příklady obou tříd.

• PTAS – Polynomial Time Approximation Scheme
• FPTAS – Fully Polynomial Time Approximation Scheme
• Rozdíl mezi PTAS a FPTAS – proč na ε záleží
• Které problémy mají PTAS/FPTAS a které ne
• Knapsack jako příklad FPTAS, TSP jako příklad PTAS