cheatsheet.org

Приближенные алгоритмы

Определения

• Задача
  • список всех ее параметров
  • формулировка свойств, которым должен удовлетворять ответ (решение) задачи
• Индивидуальная задача
  • Задача, параметрам которой присвоили конкретные значения
• Размер входа
  • Двоичное представление задачи в “наилучшей” бинарной кодировке
  • Количество бит этого представления
• Оптимизационная задача
  • максимизации или минимизации
  • множество Ω_П индивидуальных задач
  • forall I in Ω_П exists Sol_П - множество допустимых решений индивидуальной задачи I
  • функция h_П : (I in Ω_П, σ in Sol_П) -> y(I, σ) - величина решения σ
• Оптимальное решение индивидуальной задачи (минимизации) I
  • допустимое решение σ^* in Sol_п, что forall σ in Sol_п: y(I, σ^*) <= y(I, σ)
  • Y(I, σ^*) === OPT(I)
• Алгоритм
  • Множество исходных данных (Вход)
  • Последовательность инструкций
  • Для каждого допустимого входа алгоритм выполняет единственно определенную серию элементарных шагов и выдает некоторый ответ
• Время работы алгоритма
  • функция, которая каждому входу размера x ставит в соответствие максимальное по всем индивидуальным задачам время, затрачиваемое на решение индивидуальных задач данного размера
• Размер входа примера
• Полиномиальный алгоритм
  • такой алгоритм с рациональным входом, что существует целое k, что алгоритм работает время O(x^k), где x - размер входа, и все числа, используемые алгоритмом в процессе вычислений ограничены величиной O(X^k) бит
• NP-трудная задача
  • Задача П является NP-трудной, если к ней сводится некоторая NP-полная задача
• ρ-приближенный алгоритм
  • Полиномиальный алгоритм А называется ро-приближенным для задачи минимизации П, если для каждой индивидуальной задачи I A(I) <= pOPT(I).
• Полиномиальная приближенная схема (PTAS)
  • Семейство приближенных алгоритмов {A_eps}_eps
  • A_eps — (1+eps)-приближенный и время его работы ограничено полиномом от размера входа при фиксированном eps
• Вполне полиномиальная приближенная схема
  • Семейство приближенных алгоритмов {A_eps}_eps
  • A_eps — (1+eps)-приближенный и время его работы ограничено полиномом от размера входа и 1/eps
• Пропорционально-степенная функция
  • c > 0 : forall v in V w(v) = c * deg(v)
• Доминирующее множество, независимое множество, квадрат графа, циклическое покрытие, крайняя точка, разрыв двойственности
  • Доминирующим множеством в G = (V, E) называется подмножество вершин S такое, что каждая вершина в V - S смежна некоторой вершине в S
  • dom(G) - размер доминирующего множества минимальной мощности
  • Независимое множество - подмножество вершин I такое, что в нем нет смежных вершин
  • Квадрат графа - граф G^2 = (V, E’), где (u, v) in E’, когда длина пути между вершинам u и v меньше или равна 2.
  • Циклическое покрытие - набор непересекающихся циклов, покрывающих все вершины
  • Крайняя точка выпуклого множества - такая, что не является линейной комбинацией других точек
  • Разрыв двойственности: $⊃_i\frac{OPT(I)}{OPT_f(I)}$, $OPT_f(I)$ — стоимость оптимального дробного решения примера I.

Формулировки задач

• Задача линейного программирования
• Задача о вершинном покрытии
• Задача о покрытии множествами
• Задача о кратчайшей суперстроке
• Задача о минимальном остовном дереве
• Задача Штейнера
• Задача коммивояжера
• Метрическая задача о k-центрах
• Метрическая задача о взвешенных центрах
• Простейшая задача размещения
• Задача P2||Cmax
• Задача об упаковке
• Задача P||Cmax
• Цеховая задача с нефиксированными маршрутами
• Задача R||Cmax
• Задача о максимальной выполнимости

Формулировки алгоритмов

• “Простой”
• Хватала
• “Уровневный”
• Ли
• Прима
• MST
• MST-2
• Кристофидиса-Сердюкова
• Хошбаум-Шмойса
• Хошбаум-Шмойса-2
• “Суперстрока”
• Локального поиска для простейшей задачи размещения
• PTAS-1
• PTAS-2
• FPTAS
• “Первый подходящий”
• Фернандес-де-ла-Вега-Луекера
• Жадный для P||Cmax
• Жадный для O||Cmax
• Ленстры-Шмойса-Тардош
• Округление ЛП-релаксации
• Прямо двойственный алгоритм
• Вероятностный Джонсона
• Вероятностный ЛП для задачи о максимальной выполнимости
• “Перестройка расписания с прерываниями”

Формулировка теорем

• об оптимальном остовном дереве
  • T (mst) - оптимум <=> forall e = {x,y}in E(G)\E(T) все ребра из x-y-пути в Т не дороже чем e <=> forall e in E(T), e - ребро наименьшей стоимости из delta(V(C)), где C - связная компонента на T - e
• об оценке на размер доминирующего множества H, I - независимое множество в H^2. > |I| < dom(H)
• о неаппроксимируемости задачи об упаковке
  • forall eps > 0 не существует p-приближенного алгоритма для задачи об упаковке в контейнеры с rho = 3/2 - eps, если P != NP
• Вильямсона Алгоритм Гоеманса-Вильямсона - 3/4-приближенный для задачи “Максимальная выполнимость”
• первая двойственности
• вторая двойственности

Доказательство относительной оценки алгоритмов

• MST
• MST-2
• Кристофидиса-Сердюкова
• “Первый подходящий”
• Жадный для P || Cmax
• Жадный для O || Cmax

Формулировка задач ЦЛП

• R || Cmax
• о покрытии множествами
• о максимальной выполнимости