Записки программера: Видеолекции курса Алгоритмы для NP-трудных задач

Видеолекции курса Алгоритмы для NP-трудных задач.

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

Лекция 1. Введение.
Обзор курса, мотивация изучения приближённых и точных экспоненциальных алгоритмов.

Посмотреть видео на сайте Лекториума

Лекция 2. NP-полные задачи.

Задачи поиска, сведения, доказательство NP-полноты задач выполнимости, 3-выполнимости, задачи о независимом множестве, задачи о вершинном покрытии.

Литература: [DPV06, глава 8].

Посмотреть видео на сайте Лекториума

Лекция 3. Точные алгоритмы для задачи коммивояжёра и задачи о гамильтоновом цикле.

Метод динамического программирования (время: $ O^*(2^n) $ , память: ). [DPV06, глава 6]

Метод включений-исключений (время: $ O^*(2^n) $ , память: $ O^*(1) $ ). [FK10, глава 4]

Матрица Татта и перманент, решение для двудольного графа за $O^*(2^{n/2})$ времени и $ O^*(1) $ памяти. [Andreas Bjorklund. Determinant Sums for Undirected Hamiltonicity. FOCS 2010. [official], [PDF]], [Beating A Forty Year Old Result: Hamilton Cycles] [FK13]

Посмотреть видео на сайте Лекториума

Лекция 4. Приближённые алгоритмы для задачи коммивояжёра.

Лемма Шварца-Зиппеля. [wikipedia]

Приближённые алгоритмы: 1.5-приближённый алгоритм для задачи коммивояжёра в метрическом пространстве, неприближаемость общего случая, 0.5-приближение для максимизационного варианта. [CLR01, V01]

Посмотреть видео на сайте Лекториума

Лекция 5. Приближённые алгоритмы для задачи коммивояжёра (продолжение).

2/3-приближение для максимального цикла коммивояжера в ориентированном графе. [Katarzyna E. Paluch, Khaled M. Elbassioni, Anke van Zuylen: Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem. STACS 2012: 501-506. PDF]

Эвристики: метод локального поиска и метод ветвей и границ. [DPV06]

Лекция 6. Точные алгоритмы для задачи о максимальном разрезе и задачи максимальной 2-выполнимости.
Точные алгоритмы со временем работы $O^*(2^{\omega n/3})$ и памятью $O^*(2^{2n/3})$ . [Ryan Williams. Algorithms and Resource Requirements for Fundamental Problems. PhD thesis, 2007. PDF] [W03] [FK13]

Посмотреть видео на сайте Лекториума

Лекция 7. Эвристики для задачи коммивояжёра, алгоритмы для задачи о надстроке.

Эвристики для задачи коммивояжёра: метод ветвей и границ, локальный поиск. [DPV, глава 9], [пост Ричарда Липтона: Branch And Bound—Why Does It Work?]

Алгоритмы для задачи о надстроке: точный алгоритм со временем работы $ O^*(2^n) $ и полиномиальной памятью, жадная гипотеза.

Посмотреть видео на сайте Лекториума

Лекция 8. Точные алгоритмы для задачи раскраски графа.

3-раскраска: время $ O^*(2^n) $ и полиномиальная память с помощью перебора, улучшение до $ O^*(1.9^n) $ ; вероятностный $ O^*(1.5^n) $ алгоритм через сведение к задаче 2-выполнимости; $ O^*(1.45^n) $ через использование максимальных по включению независимых множеств. Общая задача: время $ O^*(3^n) $ и память $ O^*(2^n) $ через динамическое программирование, улучшение до $ O^*(2.45^n) $ через максимальные по включению независимые множества; время и память через формулу включений-исключений и быстрое преобразование Фурье. [Thore Husfeldt, Graph colouring algorithms]

Посмотреть видео на сайте Лекториума

Лекция 9. Алгоритмы для задачи выполнимости: локальный поиск.

Локальный поиск: поиск выполняющего набора в шаре радиуса $ r $ за $ O^*(3^r) $ ; оценки $O^*(3^{n/2})$ и $ O^*(1.5^n) $ с помощью покрытия шарами радиуса $ n/2 $ и $ n/4 $ .

Литература:
Uwe Schöning: A Probabilistic Algorithm for $ k $ -SAT and Constraint Satisfaction Problems. FOCS 1999: 410-414. [official, PDF]
Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravi Kannan, Jon M. Kleinberg, Christos H. Papadimitriou, Prabhakar Raghavan, Uwe Schöning: A deterministic $ (2-2/(k+1))^n $ algorithm for $ k $ -SAT based on local search. Theor. Comput. Sci. 289(1): 69-83 (2002). [official, PS]

Посмотреть видео на сайте Лекториума

Лекция 10. Алгоритмы для задачи выполнимости: метод расщепления.

DPLL-алгоритмы, основные идеи метода расщепления, вектор и число расщепления. $O^*(2^{2n/3})$ для задачи 3-выполнимости одновыполнимой формулы через расщепление относительно случайной перестановки. Запоминание дизъюнктов: решение задачи выполнимости на формулах константной плотности за $ O^*((2-c)^n) $ . Комбинированные меры сложности, measure and conquer: $O^*(2^{m/5.5})$ для задачи максимальной 2-выполнимости.

Литература:
Timon Hertli: 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General. FOCS 2011: 277-284
Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane: An improved exponential-time algorithm for k-SAT. J. ACM 52(3): 337-364 (2005)
Alexander S. Kulikov, Konstantin Kutzkov: New Bounds for MAX-SAT by Clause Learning. CSR 2007: 194-204
Arist Kojevnikov, Alexander S. Kulikov: A new approach to proving upper bounds for MAX-2-SAT. SODA 2006: 11-17

Посмотреть видео на сайте Лекториума

Лекция 11. Приближённые алгоритмы.

2-приближённый алгоритм для задачи о вершинном покрытии через максимальное по включению паросочетание, 2-приближение для взвешенного случая через линейное программирование. Жадный $\log n$ -приближённый алгоритм для задачи о покрытии множествами. $\log n$ -приближённый алгоритм для задачи о множестве представителей через линейное программирование и вероятностное округление.