Aproximačné algoritmy
(sylaby štátnic magisterského štúdia informatiky - plná verzia)
- Optimalizačné problémy
- Triedy Po a NPo
- Redukovateľnosť
- Vzťah medzi NP a NPo
- Aproximácia
- Absolútna aproximácia
- Relatívna aproximácia - trieda APX
- Lepšie ako APX: PTAS a FPTAS
- Horšie ako APX
- Asymptotická aproximácia
- Techniky návrhu aproximačných algoritmov
- Greedy algoritmy
- Lineárne programovanie
- Derandomizácia
- Vonkajškoplanárna dekompozícia
- Negatívne výsledky o aproximácii
- Pravdepodobnostne overiteľné dôkazy (PCP)
- Použitie PCPvety
- Redukcia a úplnosť v triedach aproximovateľnosti
- NPo -úplnosť
- APX-úplnosť
- Aproximovateľnosť konkrétnych problémov
- Problém obchodného cestujúceho (s trojuholníkovou nerovnosťou, metrický)
- Toky a rezy (max flow - min cut veta, zovšeobecnenia pre multikomoditné toky
a multirezy)