Uživatelské nástroje

Nástroje pro tento web


teaching:intro_par_alg2425

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:intro_par_alg2425 [2024/10/09 16:42] Martin Kouteckyteaching:intro_par_alg2425 [2024/12/17 22:45] (aktuální) – 17. 12. Martin Koutecky
Řádek 4: Řádek 4:
 ===== Tutorial sessions ===== ===== Tutorial sessions =====
  
-Tutorials are led by [[https://kam.mff.cuni.cz/~tung|Tung]].+Tutorials are led by [[https://kam.mff.cuni.cz/~tung|Tung Anh Vu]].
 [[https://iuuk.mff.cuni.cz/~tung/teaching/fpt-winter2425/|Click here for the website of the tutorials]], where [[https://iuuk.mff.cuni.cz/~tung/teaching/fpt-winter2425/|Click here for the website of the tutorials]], where
 you can find materials from the tutorial sessions and instructions on how to solve homework. you can find materials from the tutorial sessions and instructions on how to solve homework.
Řádek 14: Řádek 14:
 | 1. 10. | Introduction to parameterized algorithms / complexity. **[PA 1]**| | 1. 10. | Introduction to parameterized algorithms / complexity. **[PA 1]**|
 | 8. 10. | Kernelization **[PA 2.1, 2.2.1, 2.3-intro, 2.3.1]**. Crown decomposition lemma proof was from **[Ker, Lemma 4.5]**| | 8. 10. | Kernelization **[PA 2.1, 2.2.1, 2.3-intro, 2.3.1]**. Crown decomposition lemma proof was from **[Ker, Lemma 4.5]**|
-| 15. 10. |//Plan: finish $2k$-vertex kernel for <typo fv:small-caps>Vertex Cover</typo> **[PA 2.5]**. Bounded Search Trees: <typo fv:small-caps>Vertex Cover</typo> in $\mathcal{O}^*(1.6181^k)$ and $\mathcal{O}^*(1.4656^k)$ time; <typo fv:small-caps>Closest String</typo> in $\mathcal{O}^*(d^d)$ time **[PA 3.13.5]**//+| 15. 10. | FPT algorithm for <typo fv:small-caps>Vertex Cover above LP **[PA 3.4]**</typo>,
- +22. 10. | Bounded Search Trees: <typo fv:small-caps>Vertex Cover</typo> in $\mathcal{O}^*(1.6181^k)$ and $\mathcal{O}^*(1.4656^k)$ time; <typo fv:small-caps>Closest String</typo> in $\mathcal{O}^*(d^d)$ time **[PA 3.1, 3.5]** | 
-/*19. 10. | Finishing kernels from last time. Bounded Search Trees: <typo fv:small-caps>Vertex Cover</typo> in $\mathcal{O}^*(1.6181^k)$ and $\mathcal{O}^*(1.4656^k)$ time; <typo fv:small-caps>Closest String</typo> in $\mathcal{O}^*(d^d)$ time **[PA 3.1, 3.5]**| +29. 10. | Iterative Compression for <typo fv:small-caps>Vertex Cover</typo>, <typo fv:small-caps>Feedback Vertex Set</typo> and <typo fv:small-caps>Odd Cycle Transversal</typo>, **[PA 4.1, 4.3.1, 4.4]** | 
-26. 10. | FPT algorithm for <typo fv:small-caps>Vertex Cover above LP</typo>, application: FPT algorithm for <typo fv:small-caps>Odd Cycle Transversal</typo> **[PA 3.4]**; | +5. 11. | //sport day - no class//| 
-| 2. 11. | **No class: [[https://www.mff.cuni.cz/en/internal-affairs/dean-s-day/2023|Dean's sport day]]**| +| 12. 11. | Dynamic programming and convolutions on <typo fv:small-caps>Set Cover</typo> and <typo fv:small-caps>Steiner Tree</typo> **[PA 6.1]**, PIE and <typo fv:small-caps>Hamiltonian Cycle</typo> **[PA 10.1.1]** | 
-| 9. 11. | Iterative Compression for <typo fv:small-caps>Vertex Cover</typo>, <typo fv:small-caps>Feedback Vertex Set</typo> and <typo fv:small-caps>Odd Cycle Transversal</typo>, **[PA 4.1, 4.3.1, 4.4]** | +19. 11. | Treewidth, nice tree decompositions, <typo fv:small-caps>Independent Set</typo> **[PA 7.2, 7.3.1]**| 
-16. 11. | Dynamic programming and convolutions on <typo fv:small-caps>Set Cover</typo> and <typo fv:small-caps>Steiner Tree</typo> **[PA 6.1]**, PIE and <typo fv:small-caps>Hamiltonian Cycle</typo> **[PA 10.1.1]** | +26. 11. | More Treewidth - gridsbidimensionality **[PA 7.7.1, 7.7.2 ]**| 
-23. 11. | Treewidth, nice tree decompositions, <typo fv:small-caps>Independent Set</typo> **[PA 7.2, 7.3.1]**| +3. 12. | Intro to neighborhood diversity and ILPs. Solving <typo fv:small-caps>Coloring</typo> on graphs of bounded $nd(G)$. **[ND, NdCol, 5M]**| 
-30. 11. | More Treewidth - FPT alg.MSO, grids **[PA 7.7.1, 7.7.2 ]**| +10. 12. | Neighborhood diversity: <typo fv:small-caps>Sum Coloring</typo> via $n$-fold IP, and as a convex IP in small dimension **[5M, Thm 2(a), 2(b)]**| 
-7. 12. | Intro to neighborhood diversity and ILPs. Solving <typo fv:small-caps>Coloring</typo> on graphs of bounded $nd(G)$. **[ND, NdCol, 5M]**| +17. 12. | Plan: Neighborhood diversity: Q&A on <typo fv:small-caps>Sum Coloring</typo> **[5M, Thm 2]**, <typo fv:small-caps>Capacitated Dominating Set</typo> **[5M, Thm 1]**; <typo fv:small-caps>Max $q$-Cut</typo> **[5MThm 3]**. [[https://www.geogebra.org/calculator/pfdttsng|Geogebra: $x \cdot y$ is obviously not convex.]]
-14. 12. | Neighborhood diversity: <typo fv:small-caps>Sum Coloring</typo> via $n$-fold IP, and as a convex IP in small dimension **[5M, Thm 2(a), 2(b)]**| +7. 1. | //Plan: $P||C_{\max}$ is FPT($d$) if $p_{\max}$ unary bounded, using the algorithm of Goemans-Rothvoss **[GR]**. Another application: <typo fv:small-caps>Equitable Coloring</typo> is FPT($nd(G)$).//|
-21. 12. | Neighborhood diversity: finish <typo fv:small-caps>Sum Coloring</typo> **[5M, Thm 2]**, <typo fv:small-caps>Capacitated Dominating Set</typo> **[5M, Thm 1]**+
-| 4. 1. | Parameterized reductions, The W-hierarchy **[PA13.1, 13.2, 13.3]**| +
-11. 1. | $P||C_{\max}$ is FPT($d$) if $p_{\max}$ unary bounded, using the algorithm of Goemans-Rothvoss **[GR]**. Another application: <typo fv:small-caps>Equitable Coloring</typo> is FPT($nd(G)$). |*/+
  
 ===== Materials ===== ===== Materials =====
teaching/intro_par_alg2425.1728484940.txt.gz · Poslední úprava: 2024/10/09 16:42 autor: Martin Koutecky