Параметризованные алгоритмы весна 2018 — различия между версиями
Материал из SEWiki
Bliznets (обсуждение | вклад) (→Лекции) |
Bliznets (обсуждение | вклад) (→Лекции) |
||
| (не показано 16 промежуточных версий этого же участника) | |||
| Строка 8: | Строка 8: | ||
**Feedback Arc Set in Tournaments. Edge Clique Cover. Crown Decomposition. Vertex Cover. Maximum Satisfiability. | **Feedback Arc Set in Tournaments. Edge Clique Cover. Crown Decomposition. Vertex Cover. Maximum Satisfiability. | ||
*16 march. Sunflower lemma. Kernelization for Vertex Cover using LP. Vertex Cover above LP branching. | *16 march. Sunflower lemma. Kernelization for Vertex Cover using LP. Vertex Cover above LP branching. | ||
| − | *23 march. Iterative Compression. | + | *23 march. Vertex Cover above Matching. Iterative Compression. |
| + | ** Odd Cycle transversal <math>O^*(4^k)</math>. Variable Deletion Almost 2-SAT. Feedback Vertex Set in Tournaments. Feedback Vertex Set. Odd Cycle Transversal <math>O^*(3^k)</math>. | ||
| + | *30 march. Randomized methods. | ||
| + | *6 april. <math>O^*(4^k)</math> algorithm for k-path. Derandomization. | ||
| + | *13 april. Dynamic programming over subsets. Integer linear programming. Graph minors and Robertson-Seymour theorem. | ||
| + | *20 april. Important cuts. Edge Multiway Cut. | ||
| + | *27 april. Important cuts in Directed graphs. Directed Feedback Vertex Set. | ||
| + | *04 may. W[1] class. | ||
| + | *11 may. Kernel lower bounds. | ||
| + | *18 may. Vertex cover does not admit subquadratic bit size kernel. | ||
== Практика == | == Практика == | ||
| Строка 19: | Строка 28: | ||
*[[Медиа:FPT-class-4.pdf|23 march, "Iterative Compression."]] | *[[Медиа:FPT-class-4.pdf|23 march, "Iterative Compression."]] | ||
*[[Медиа:FPT-home-4.pdf|23 march, "Iterative Compression(HW)."]] | *[[Медиа:FPT-home-4.pdf|23 march, "Iterative Compression(HW)."]] | ||
| + | *[[Медиа:FPT-class-5.pdf|30 march, "Randomized methods."]] | ||
| + | *[[Медиа:FPT-home-5.pdf|30 march, "Randomized methods(HW)."]] | ||
| + | *[[Медиа:FPT-class-6.pdf|06 april, "Derandomization."]] | ||
| + | *[[Медиа:FPT-home-6.pdf|06 april, "Randomized methods and derandomization(HW)."]] | ||
| + | *[[Медиа:FPT-home-13.pdf|13 april, "Miscellaneous(HW)."]] | ||
| + | *[[Медиа:FPT-home-8.pdf|20 april, "Important cuts(HW)."]] | ||
| + | *[[Медиа:FPT-class-9.pdf|27 april, "Important cuts II."]] | ||
| + | *[[Медиа:FPT-home-9.pdf|27 april, "Important cuts II(HW)."]] | ||
| + | *[[Медиа:FPT-class-10.pdf|03 may, "W[1], W[2]."]] | ||
| + | *[[Медиа:FPT-home-10.pdf|03 may, "W[1], W[2](HW)."]] | ||
Текущая версия на 18:32, 3 июня 2018
Преподаватель: Близнец Иван Анатольевич (iabliznets@gmail.com)
Лекции
- 16 february. Bounded search trees.
- FPT. Kernelization. Vertex Cover. Feedback Vertex Set. Closest String.
- 2 march. Kernelization.
- Feedback Arc Set in Tournaments. Edge Clique Cover. Crown Decomposition. Vertex Cover. Maximum Satisfiability.
- 16 march. Sunflower lemma. Kernelization for Vertex Cover using LP. Vertex Cover above LP branching.
- 23 march. Vertex Cover above Matching. Iterative Compression.
- Odd Cycle transversal . Variable Deletion Almost 2-SAT. Feedback Vertex Set in Tournaments. Feedback Vertex Set. Odd Cycle Transversal .
- 30 march. Randomized methods.
- 6 april. algorithm for k-path. Derandomization.
- 13 april. Dynamic programming over subsets. Integer linear programming. Graph minors and Robertson-Seymour theorem.
- 20 april. Important cuts. Edge Multiway Cut.
- 27 april. Important cuts in Directed graphs. Directed Feedback Vertex Set.
- 04 may. W[1] class.
- 11 may. Kernel lower bounds.
- 18 may. Vertex cover does not admit subquadratic bit size kernel.
Практика
Надо оформить 5 самых сложных задач из Вами решенных.
- 2 march, "Kernelization."
- 2 march, "Kernelization(HW)."
- 16 march, "Kernelization II(HW)."
- 23 march, "Iterative Compression."
- 23 march, "Iterative Compression(HW)."
- 30 march, "Randomized methods."
- 30 march, "Randomized methods(HW)."
- 06 april, "Derandomization."
- 06 april, "Randomized methods and derandomization(HW)."
- 13 april, "Miscellaneous(HW)."
- 20 april, "Important cuts(HW)."
- 27 april, "Important cuts II."
- 27 april, "Important cuts II(HW)."
- 03 may, "W[1], W[2]."
- 03 may, "W[1], W[2](HW)."
