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 | ПОМИ РАН | slides, video, files |
| 13 September 11:40–13:10 |
Обзор, Lecture | ПОМИ РАН | slides, video, files |
| 25 October 10:20–11:50 |
NP-полные задачи, Lecture | ПОМИ РАН | slides, video, files |
| 25 October 11:40–13:10 |
Вероятностные алгоритмы, Lecture | ПОМИ РАН | slides, video, files |
| 01 November 10:30–12:00 |
Приближенные алгоритмы, Lecture | ПОМИ РАН | slides, video, files |
| 01 November 12:10–13:40 |
Приближенные алгоритмы, Lecture | ПОМИ РАН | slides, video, files |
| 01 November 14:00–15:30 |
Приближенные алгоритмы, Lecture | ПОМИ РАН | slides, video, files |
| 08 November 10:35–12:05 |
Алгоритмы расщепления, Lecture | ПОМИ РАН | slides, video, files |
| 08 November 10:40–12:10 |
Алгоритмы расщепления, Lecture | ПОМИ РАН | slides, video, files |
| 29 November 10:45–12:15 |
Точные и FPT-алгоритмы, Lecture | ПОМИ РАН | slides, video, files |
| 06 December 10:50–12:20 |
FPT-алгоритмы, Lecture | ПОМИ РАН | slides, video, files |
