# **NDMI018** Aproximační a online algoritmy

<{Box(infobox)}>
|-----|-----|
| **Stránka předmětu:** | [Web](http://iuuk.mff.cuni.cz/~sgall/vyuka/APX/) |
| **Přednášející:** | [prof. RNDr. Jiří Sgall, DrSc.](https://iuuk.mff.cuni.cz/~sgall/) |
| **Cvičící:** | [Mgr. Cyril Kotecký](https://is.cuni.cz/studium/predmety/index.php?tid=&do=ucit&kod=93912) |
| **Odkaz do SISu:** | [NDMI018](https://is.cuni.cz/studium/predmety/index.php?do=predmet&kod=NDMI018) |
<{/Box}>

## Skripta a záznamy
- [Aktuální ročník](https://iuuk.mff.cuni.cz/%7Esgall/vyuka/APX/)
- [Záznamy z COVIDu](https://iuuk.mff.cuni.cz/%7Esgall/vyuka/APX/APX20.html)
- [Poznámky kouril.dev](https://kouril.dev/aprox_alg/)
- [Fotky studentských poznámek](https://drive.google.com/drive/folders/1ZNmO1xVpOKdovwnT_EsXOWh1GCIh4GLP?usp=sharing)

## Otázky od zkoušky

Je třeba vědět co napsat a pak umět o problému přemýšlet, protože vždycky se ptá.
Nejde o kompletní výčet, spíše pro představu, jak moc do hloubky se jde.
V "nebo" případech se může lehce zeptat i na druhou podčást.

- Steiner tree
- PTAS - Scheduling nebo Bin packing
- Randomizované stránování, $2H_n$-kompetitivní algoritmus
- Konstrukce tree metriky
- Lower bound pro k-server - k-kompetitivnost
- PCP theorem, jak z něj plyne neexistence PTAS pro MAX-SAT
- k-server: lower bound pro obecnou metriku nebo upper bound pro tree metriku