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í verzeNásledující verze | Předchozí verze | ||
teaching:ads22223_lecture [2023/01/03 10:37] – Martin Koutecky | teaching:ads22223_lecture [2023/01/09 13:41] (aktuální) – Martin Koutecky | ||
---|---|---|---|
Řádek 20: | Řádek 20: | ||
| 14. 12. | Reductions: SAT, 3-SAT, IndSet, Clique, 3DM. [[https:// | | 14. 12. | Reductions: SAT, 3-SAT, IndSet, Clique, 3DM. [[https:// | ||
| 21. 12. | 3,3-SAT reduces to 3DM. Classes P, NP; Cook's theorem. [[https:// | | 21. 12. | 3,3-SAT reduces to 3DM. Classes P, NP; Cook's theorem. [[https:// | ||
+ | | 4. 1. | Dealing with NP-hardness. IndSet is solvable on trees; coloring is solvable on interval graphs; Knapsack is solvable in pseudopolynomial time (=when input values are polynomially bounded). Approximation: | ||
{{page> | {{page> | ||
+ | * {{ : | ||
Řádek 65: | Řá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.1672738625.txt.gz · Poslední úprava: 2023/01/03 10:37 autor: Martin Koutecky