Аппроксимирующие алгоритмы

После обсуждения NP-полноты и концепции вычислительной неразрешимости в целом мы начали искать ответ на фундаментальный вопрос: как разрабатывать алгоритмы для задач, у которых полиномиальное время, скорее всего, является недостижимым?

В этом определении следует обратить внимание на ключевые слова: гарантированно и близкие. Мы не пытаемся искать оптимальное решение, и в результате появляется возможность достичь полиномиального времени выполнения.

В то же время нужно будет доказывать, что алгоритмы находят решения, гарантированно близкие к оптимуму. Эта задача весьма непростая по своей природе: чтобы доказать гарантию аппроксимации, необходимо сравнить решение с оптимальным решением, которое очень трудно найти (и, возможно, привести обоснование). Данная проблема неоднократно встречается при анализе алгоритмов в этой главе.

В этой главе рассматриваются четыре общие методологии разработки аппроксимирующих алгоритмов.

Эти алгоритмы быстры и просты, как и в главе 4, поэтому основная проблема связана с поиском жадного правила, приводящего  к решению, доказуемо близкого к оптимальному.

Второй общий метод — метод назначения цены — имеет экономическую подоплеку; мы рассматриваем цену, которую необходимо уплатить за соблюдение каждого ограничения в задаче.

Метод назначения цены часто называется прямо-двойственным методом (primal-dual) — термин происходит из области линейного программирования, которое тоже может использоваться в этой области.

Описание метода назначения цены не требует знакомства с линейным программированием, которое будет представлено  в третьей категории — линейном программировании с округлением, использующем отношения между вычислительной разрешимостью линейного программирования и выразительной мощью его «более сложного» родственника, целочисленного программирования.

В завершение будет описан метод, приводящий к исключительно качественным аппроксимациям: применение динамического программирования к округленной версии входных данных.