teaching:ads22223_lecture
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
Obě strany předchozí revizePředchozí verze | |||
teaching:ads22223_lecture [2023/01/09 13:36] – Martin Koutecky | teaching:ads22223_lecture [2023/01/09 13:41] (aktuální) – Martin Koutecky | ||
---|---|---|---|
Řádek 67: | Řádek 67: | ||
* P, NP, NP-complete, | * P, NP, NP-complete, | ||
* Cook's theorem | * Cook's theorem | ||
- | * Approximation algorithms | + | |
- | * TBA | + | * IndSet on Trees |
+ | * Coloring of Interval Graphs | ||
+ | | ||
+ | * $2$-approximation of $\Delta$-TSP | ||
+ | * Non-existence of an $O(1)$-approximation for (unrestricted) TSP | ||
+ | * Pseudopolynomial algorithm for Knapsack; FPTAS for Knapsack. | ||
teaching/ads22223_lecture.1673267800.txt.gz · Poslední úprava: 2023/01/09 13:36 autor: Martin Koutecky