Алгоритмы для NP-трудных задач

Общая информация
ЛекторА. С. Куликов
Семестросень 2013
Дата начала15.09.2013
Количество пар12
Язык курсарусский
Вопросы к экзамену
Аннотация

В курсе будет дан обзор идей и методов, использующихся при построении и анализе алгоритмов для 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. Введение
(15.09.2013 - 11:15 - 12:50)

Обзор курса, мотивация изучения приближённых и точных экспоненциальных алгоритмов. http://www.youtube.com/embed/QBS1N9LU4tI
2. NP-полные задачи
(22.09.2013 - 11:15 - 13:00)

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

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

http://youtu.be/nW6wMMdp7ag
3. Точные алгоритмы для задачи коммивояжёра и задачи о гамильтоновом цикле
(22.09.2013 - 13:00 - 14:35)

Метод динамического программирования (время: $ O^*(2^n) $, память: $ 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]

http://youtu.be/DefCPIG0RUo
4. Приближённые алгоритмы для задачи коммивояжёра
(06.10.2013 - 11:15 - 12:50)

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

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

http://www.youtube.com/embed/1p_Ci1HCwEA
5. Приближённые алгоритмы для задачи коммивояжёра (продолжение)
(13.10.2013 - 11:15 - 12:50)

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-выполнимости
(13.10.2013 - 13:00 - 14:35)

Точные алгоритмы со временем работы $ O^*(2^{\omega n/3}) $ и памятью $ O^*(2^{2n/3}) $. [Ryan Williams. Algorithms and Resource Requirements for Fundamental Problems. PhD thesis, 2007. PDF] [W03] [FK13] http://www.youtube.com/embed/wr4ZAbNc4vQ
7. Эвристики для задачи коммивояжёра, алгоритмы для задачи о надстроке
(27.10.2013 - 11:15 - 12:50)

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

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

http://www.youtube.com/embed/YvFiHsyZMmM
8. Точные алгоритмы для задачи раскраски графа
(27.10.2013 - 13:00 - 14:35)

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) $ через максимальные по включению независимые множества; время и память $ O^*(2^n) $ через формулу включений-исключений и быстрое преобразование Фурье. [Thore Husfeldt, Graph colouring algorithms]

http://www.youtube.com/embed/3016b04di-k
9. Алгоритмы для задачи выполнимости: локальный поиск
(10.11.2013 - 11:15 - 12:50)

Локальный поиск: поиск выполняющего набора в шаре радиуса $ 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]

http://www.youtube.com/embed/5KqF9DS4MvI
10. Алгоритмы для задачи выполнимости: метод расщепления
(10.11.2013 - 13:00 - 14:35)

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

http://www.youtube.com/embed/W_XFRE2HNAo
11. Приближённые алгоритмы
(17.11.2013 - 11:15 - 12:50)

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

http://www.youtube.com/embed/Gx3ZWuKLuno
12. Приближённые алгоритмы
(17.11.2013 - 13:00 - 14:35)

4-приближённый алгоритм для задачи о кратчайшей общей надстроке через покрытие циклами.

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

http://www.youtube.com/embed/JarpkhTjTr8
Голосов пока нет
Share |