| Obě strany předchozí revizePředchozí verzeNásledující verze | Předchozí verze |
| teaching:ads22223_lecture [2023/01/04 12:45] – Martin Koutecky | teaching:ads22223_lecture [2023/01/09 13:41] (aktuální) – Martin Koutecky |
|---|
| | 14. 12. | Reductions: SAT, 3-SAT, IndSet, Clique, 3DM. [[https://stream.cuni.cz/cs/Detail/18529|recording]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-9.pdf|slides]], [[https://jeffe.cs.illinois.edu/teaching/algorithms/book/12-nphard.pdf|JeffE (more than you asked for)]]| | | 14. 12. | Reductions: SAT, 3-SAT, IndSet, Clique, 3DM. [[https://stream.cuni.cz/cs/Detail/18529|recording]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-9.pdf|slides]], [[https://jeffe.cs.illinois.edu/teaching/algorithms/book/12-nphard.pdf|JeffE (more than you asked for)]]| |
| | 21. 12. | 3,3-SAT reduces to 3DM. Classes P, NP; Cook's theorem. [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-10.pdf|slides]], [[https://jeffe.cs.illinois.edu/teaching/algorithms/book/12-nphard.pdf|JeffE]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2-21122022.mkv|recording]]| | | 21. 12. | 3,3-SAT reduces to 3DM. Classes P, NP; Cook's theorem. [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-10.pdf|slides]], [[https://jeffe.cs.illinois.edu/teaching/algorithms/book/12-nphard.pdf|JeffE]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2-21122022.mkv|recording]]| |
| | 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: 2-approximation algorithm for $\Delta$-TSP (on a complete graph and with $\Delta$-inequality). No $\alpha$-approximation for general TSP. Fully polynomial time approximation scheme (FPTAS) for Knapsack (downscaling values). [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-10.pdf|slides 1]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-11.pdf|slides 2]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2-01042023.mkv|recording]]| | | 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: 2-approximation algorithm for $\Delta$-TSP (on a complete graph and with $\Delta$-inequality). No $\alpha$-approximation for general TSP. Fully polynomial time approximation scheme (FPTAS) for Knapsack (downscaling values). [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-10.pdf|slides 1]], [[https://iuuk.mff.cuni.cz/~hubicka/2020/adsII-11.pdf|slides 2]], [[https://iuuk.mff.cuni.cz/~koutecky/ads2-04012023.mkv|recording]]| |
| |
| |
| {{page>teaching:bits:resources_ads1}} | {{page>teaching:bits:resources_ads1}} |
| | * {{ :teaching:ads22223:ads2_lecture_notes.pdf |Notes from Andrej Perković}} (**100MB file**) (no guarantee of correctness, email him if you find bugs: <arachneen_octogone.0c@icloud.com>) |
| |
| |
| * P, NP, NP-complete, NP-hard | * P, NP, NP-complete, NP-hard |
| * Cook's theorem | * Cook's theorem |
| * Approximation algorithms | * Dealing with NP-hardness |
| * TBA | * IndSet on Trees |
| | * Coloring of Interval Graphs |
| | * Approximation algorithms (definition) |
| | * $2$-approximation of $\Delta$-TSP |
| | * Non-existence of an $O(1)$-approximation for (unrestricted) TSP |
| | * Pseudopolynomial algorithm for Knapsack; FPTAS for Knapsack. |
| |
| |
