Uživatelské nástroje

Nástroje pro tento web


teaching:ads22223_lecture

Rozdíly

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

Odkaz na výstup diff

Obě strany předchozí revizePředchozí verze
Následující verze
Předchozí verze
teaching:ads22223_lecture [2023/01/05 14:09] Martin Kouteckyteaching:ads22223_lecture [2023/01/09 13:41] (aktuální) Martin Koutecky
Řádek 24: Řádek 24:
  
 {{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>)
  
  
Řádek 66: Řádek 67:
     * 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.
  
  
teaching/ads22223_lecture.1672924174.txt.gz · Poslední úprava: 2023/01/05 14:09 autor: Martin Koutecky