Эффективные алгоритмы

Будут рассмотрены три типа алгоритмов, которым обычно уделяется мало внимания в стандартных курсах, а именно: вероятностные алгоритмы для задач из класса P, точные алгоритмы для NP-трудных задач, приближённые алгоритмы для NP-трудных задач. Многие из рассмотренных нами алгоритмов будут лучшими (в смысле теоретических оценок на качество) из известных на данный момент. В то же время мы постараемся узнать не как можно лучшие оценки для рассматриваемых задач, а побольше различных методов для получения оценок.

1 Вероятностные алгоритмы
  1.1 Сравнение строк: односторонняя вероятность ошибки $1/n$ при пересылке $\log n$ битов; поиск подстроки
  1.2 Проверка результата перемножения матриц: односторонняя вероятность ошибки $1/2$ за время $n^2$ через умножение на случайный вектор
  1.3 Проверка равенства нулю многочлена: односторонняя ошибка $1/2$ через вычисление в случайных точках
  1.4 Проверка числа на простоту
  1.5 Минимальный разрез
  1.6 Кратчайшие пути между всеми парами вершин
  1.7 Минимальное покрывающее дерево

2 Алгоритмы для NP-трудных задач
  2.1 Максимальное независимое множество: перечисление всех максимальных по включению независимых множеств за $3^{n/3}$
  2.2 Формула включений-исключений: преобразования на решётке подмножеств; алгоритм Иейтса
  2.3 Максимальная 2-выполнимость: $2^{\omega n/3}$ и экспоненциальная память через быстрое умножение матриц
  2.4 Максимальный разрез: $2^{\omega n/3}$ и экспоненциальная память через быстрое нахождение треугольников
  2.5 Хроматическое число: $3^n$ и экспоненциальная память через динамическое программирование, улучшение до $2.45^n$; $2^n$ и экспоненциальная память через формулу включений-исключений; $3$-раскраска за $1.5^n$ через сведение к $2$-выполнимости
  2.6 Гамильтонов цикл: $2^n$ и экспоненциальная память для ориентированных графов через динамическое программирование; $2^n$ для ориентированных графов через формулу включений-исключений; $2^{n/2}$ для двудольных графов через покрытия помеченными циклами
  2.7 Выполнимость: $2^{2n/3}$ для $3$-выполнимости через расщепление относительно случайной перестановки переменных; $1.5^n$ для $3$-выполнимости через покрытие шарами; быстрее $2^n$ для формул константной плотности

3 Приближённые алгоритмы для NP-трудных задач
  3.1 Вершинное покрытие: $2$-приближение через нахождение максимального по включению паросочетания; $2$-приближение для взвешенного случая через линейное программирование
  3.2 Покрытие множествами: $\log n$-приближение через жадность; $\log n$-приближение для взвешенного случая
  3.3 Множество представителей: $\log n$-приближение через линейное программирование
  3.4 Минимальный путь коммивояжёра в метрическом пространстве: $2$-приближение через минимальное покрывающее дерево; $3/2$-приближение через нахождение совершенного паросочетания минимального веса; неприближаемость общего случая
  3.5 Максимальный путь коммивояжёра: $2/3$-приближение через покрытие вершин циклами с полурёбрами
  3.6 Кратчайшая надстрока: $\log n$-приближение через сведение к покрытию множествами; $4$-приближение через покрытие вершин префикс-графа направленными циклами; $2\frac{2}{3}$-приближение через сведение к MAX-ATSP
  3.7 Рюкзак: псевдополиномиальный алгоритм; полностью полиномиальная приближённая схема
  3.8 Максимальный разрез: задача полуопределённого программирования; $0.878$-приближение через полуопределённое программирование
  3.9 Хроматическое число: $\sqrt{n}$-приближение для $3$-раскрашиваемого графа через жадность; $n^{0.39}$-приближение для $3$-раскрашиваемого графа через полуопределённое программирование
  3.9 Максимальная $2$-выполнимость: $0.75$-приближение через случайную подстановку; $0.878$-приближение через полуопределённое программирование