Параметризованные алгоритмы весна 2018 — различия между версиями

Материал из SEWiki
Перейти к: навигация, поиск
(Лекции)
(Лекции)
 
(не показано 28 промежуточных версий этого же участника)
Строка 3: Строка 3:
 
== Лекции ==
 
== Лекции ==
  
*16 февраля. Bounded search trees.
+
*16 february. Bounded search trees.
*2 марта. Kernelization.
+
** 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.
 
**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 <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.
  
 
== Практика ==
 
== Практика ==
  
*[[Медиа:FPT-home-1.pdf|16 февраля, "Bounded search trees."]]
+
*[[Медиа:FPT-home-1.pdf|16 february, "Bounded search trees (HW)."]]
 
+
 
Надо оформить 5 самых сложных задач из Вами решенных.
 
Надо оформить 5 самых сложных задач из Вами решенных.
 +
*[[Медиа:FPT-class-2.pdf|2 march, "Kernelization."]]
 +
*[[Медиа:FPT-home-2.pdf|2 march, "Kernelization(HW)."]]
 +
*[[Медиа:FPT-home-3.pdf|16 march, "Kernelization II(HW)."]]
 +
*[[Медиа:FPT-class-4.pdf|23 march, "Iterative Compression."]]
 +
*[[Медиа: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 самых сложных задач из Вами решенных.