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

Лектор: Александр Сергеевич Куликов

Язык курса: русский

Краткое описание курса:
В курсе будут рассмотрены красивые идеи построения алгоритмов для NP–трудных задач — от классических до недавних результатов. Предварительный список тем: точные алгоритмы (расщепление, локальный поиск, умный перебор, сведение к простой задаче), fixed parameter tractable алгоритмы (kernelization, color coding, алгоритмы, основанные на матричном умножении и формуле включений–исключений), приближённые алгоритмы (алгоритмы, основанные на линейном и полуопределённом программировании).

Название Слайды Версия для печати Видео Содержание лекции
1. Обзор. pdf pdf tube, mp4 P и NP неформально. Точные алгоритмы. $ \sqrt{3}^n $ алгоритм, основанный на локальном поиске, для задачи выполнимости. $ 1.732^n $ алгоритм для задачи о максимальном разрезе, использующий быстрое умножение матриц для нахождения треугольников.
2. Обзор. pdf pdf tube, mp4 FPT алгоритмы. Kernelization. $ k(k+1) $ ядро для задачи о покрытии точек прямыми. $ k(k+1) $ ядро для задачи о вершинном покрытии, основанное на простых правилах упрощениях, и $ 4k $ ядро, основанное на crown decomposition lemma. Приближённые алгоритмы. 2–оптимальный алгоритм для задачи о вершинном покрытии. 2–оптимальный алгоритм для задачи о коммивояжере в метрическом пространстве.
3. NP–полные задачи. pdf pdf tube, avi Задачи поиска, NP–полные задачи, сведения.
4. Вероятностные алгоритмы. pdf pdf tube, avi $ 1.5^n $ алгоритм для задачи о 3–раскрашиваемости графа. $ \log(2n) $–приближенный алгоритм для задачи о минимальном множестве представителей. FPT–алгоритм для задачи о пути длины $ k $. $ 2^{2n/3} $ алгоритм для 3–SAT.
5. Приближенные алгоритмы. pdf pdf tube, avi $ \log{n} $–приближенный алгоритм для задачи о покрытии множествами, $ 2\log{n} $–приближенный алгоритм для задачи о кратчайшей надпоследовательности.
6. Приближенные алгоритмы. pdf pdf tube, avi $ 3/2 $–приближенный алгоритм для задачи о коммивояжере в метрическом пространстве, неприближаемость задачи о коммивояжере, полностью полиномиальная приближенная схема для задачи о рюкзаке.
7. Приближенные алгоритмы. pdf pdf tube, avi Приближенные алгоритмы, основанные на решении задачи полуопределенного программирования. $ 0.87 $–приближенный алгоритм для задачи о максимальном разрезе, раскраска вершин $ 3 $–раскрашиваемого графа в $ O(d^{0.631}) $ цветов, где $ d $ — средняя степень вершин графа.
8. Алгоритмы расщепления. pdf pdf tube Оценка времени работы алгоритмов расщепления, правила упрощения, простой $ 1.415^K $, где $ K $ — количество клозов, алгоритм, основанный на методе расщепления, для задачи выполнимости, автоматический анализ времени работы.
9. Алгоритмы расщепления. pdf pdf tube, avi Комбинированные меры сложности, верхняя оценка $ 2^{K/5.5} $ для задачи максимальной 2–выполнимости, запоминание дизъюнктов, решение задачи выполнимости формул константной плотности быстрее чем за $ 2^n $ шагов.
10. Точные алгоритмы. pdf pdf Формула включений–исключений. Задача о гамильтоновом пути, задача о количестве совершенных паросочетаний. Сведение к простой задаче. Задача о сумме подмножества, задача максимальной 2–выполнимости.
11. FPT–алгоритмы. pdf pdf Лемма о подсолнухе. Задача о минимальном множестве представителей. Динамическое программирование. Задача о дереве Штайнера. Итеративное сжатие. Задача об удалении нечетных циклов.




Ссылки по теме