City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Algorithms for NP-hard problems
Saint Petersburg / autumn 2013, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

В курсе будет дан обзор идей и методов, использующихся при построении и анализе алгоритмов для 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]

Date and time Class|Name Venue|short Materials
15 September
11:15–12:50
Введение, Lecture ПОМИ РАН video
22 September
11:15–13:00
NP-полные задачи, Lecture ПОМИ РАН video
22 September
13:00–14:35
Точные алгоритмы для задачи коммивояжёра и задачи о гамильтоновом цикле, Lecture ПОМИ РАН video
06 October
11:15–12:50
Приближённые алгоритмы для задачи коммивояжёра, Lecture ПОМИ РАН video
13 October
11:15–12:50
Приближённые алгоритмы для задачи коммивояжёра (продолжение), Lecture ПОМИ РАН video
13 October
13:00–14:35
Точные алгоритмы для задачи о максимальном разрезе и задачи максимальной 2-выполнимости, Lecture ПОМИ РАН video
27 October
11:15–12:50
Эвристики для задачи коммивояжёра, алгоритмы для задачи о надстроке, Lecture ПОМИ РАН No
27 October
13:00–14:35
Точные алгоритмы для задачи раскраски графа, Lecture ПОМИ РАН video,  files
10 November
11:15–12:50
Алгоритмы для задачи выполнимости: локальный поиск, Lecture ПОМИ РАН video,  files
10 November
13:00–14:35
Алгоритмы для задачи выполнимости: метод расщепления, Lecture ПОМИ РАН video
17 November
11:15–12:50
Приближённые алгоритмы, Lecture ПОМИ РАН video
17 November
13:00–14:35
Приближённые алгоритмы, Lecture ПОМИ РАН video