В курсе будет дан обзор идей и методов, использующихся при построении и анализе алгоритмов для NP-трудных задач. Несмотря на то что эффективных алгоритмов для таких задач до сих пор неизвестно, NP-трудные задачи часто возникают на практике. Мы рассмотрим приближённые алгоритмы (позволяющие эффективно находить решение, которое гарантированно не сильно хуже оптимального), точные алгоритмы с доказуемыми верхними оценками (которые более интересны с теоретической точки зрения) и эвристики (алгоритмы, хорошо работающие на практике, но не имеющие теоретических гарантий на время работы и ошибку приближения).

Отдельное внимание будет уделено открытым задачам данной области.

Курс предполагает знакомство слушателей лишь с базовыми алгоритмическими идеями.

Основная литература:

• Книги:
  1. [FK10] Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Springer. 2010. [official]
  2. [V01] Vijay V. Vazirani. Approximation Algorithms. Springer. 2001. [official], [PDF]
  3. [WS11] David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press. 2011. [official], [PDF]
  4. [DPV06] Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani. Algorithms. McGraw-Hill. 2006. [official], [PDF]
  5. [CLR01] Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест. Алгоритмы: построение и анализ. Издательство МЦНМО. 2001.
• Обзоры:
  1. [W03] Gerhard J. Woeginger. Exact algorithms for NP-hard problems: a survey. Combinatorial optimization - Eureka, you shrink! Springer. 2003. [official], [PDF]
  2. [FK13] Fedor V. Fomin, Petteri Kaski. Exact exponential algorithms. Communications of the ACM. 2013. [official], [PDF]
  3. [YWHL13] Dongxiao Yu, Yuexuan Wang, Qiang-Sheng Hua, Francis C.M. Lau. Faster and Space Efficient Exact Exponential Algorithms: Combinatorial and Algebraic Approaches. Handbook of Combinatorial Optimization, Springer. 2013, pp 1249-1291. [official], [PDF]
• Lecture notes:
  1. [A09] AGAPE Spring School on Fixed Parameter and Exact Algorithms. [PDF]