City: Санкт-Петербург Новосибирск Казань Language: Русский English

Algorithms for NP-hard problems
Санкт-Петербург / autumn 2009, посмотреть все семестры

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

We will consider some interesting ideas of designing algorithms for NP–hard problems — from classical to recent ones. Preliminary program: exact algorithms (splitting, local search, clever enumeration, reduction to an easy problem), fixed parameter tractable algorithms (kernelization, color coding, algorithms based on matrix multiplication and inclusion–exclusion principle), approximation algorithms (algorithms based on linear and semidefinite programming).

Links

Date and time Class|Name Venue|short Materials
13 September
10:00–11:30
Обзор, lecture ПОМИ РАН slidesvideo, files
13 September
11:40–13:10
Обзор, lecture ПОМИ РАН slidesvideo, files
25 October
10:20–11:50
NP-полные задачи, lecture ПОМИ РАН slidesvideo, files
25 October
11:40–13:10
Вероятностные алгоритмы, lecture ПОМИ РАН slidesvideo, files
01 November
10:30–12:00
Приближенные алгоритмы, lecture ПОМИ РАН slidesvideo, files
01 November
12:10–13:40
Приближенные алгоритмы, lecture ПОМИ РАН slidesvideo, files
01 November
14:00–15:30
Приближенные алгоритмы, lecture ПОМИ РАН slidesvideo, files
08 November
10:35–12:05
Алгоритмы расщепления, lecture ПОМИ РАН slidesvideo, files
08 November
10:40–12:10
Алгоритмы расщепления, lecture ПОМИ РАН slidesvideo, files
29 November
10:45–12:15
Точные и FPT-алгоритмы, lecture ПОМИ РАН slidesvideo, files
06 December
10:50–12:20
FPT-алгоритмы, lecture ПОМИ РАН slidesvideo, files