Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- 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, NP-hard
     * 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.