Аппроксимационные алгоритмы, используемые в точных алгоритмах

Алгоритмы аппроксимации могут давать результат до некоторого постоянного фактора. Это немного менее удовлетворительно, чем точные алгоритмы.

Однако постоянные факторы игнорируются во временной сложности.

Поэтому мне интересно, возможен ли или был использован следующий прием для решения некоторой проблемы :$B \circ A$

1. Используйте алгоритм аппроксимации решения задачи чтобы получить решение пределах постоянного множителя;$A$$S$
2. Используйте точный алгоритм, решающий задачу , время выполнения которой зависит от веса но работает, пока является правильным решением.S $B$$S$$S$

Таким образом, аппроксимация является «подпроцедурой» точного алгоритма, а постоянный фактор, потерянный на шаге 1, поглощается на шаге 2.

Примером параметризованной сложности является ядро для задачи покрытия вершин с использованием теоремы Немхаузера и Троттера.

В задаче о минимальном покрытии вершин нам дан неориентированный граф G, и нам нужно найти покрытие вершин G минимального размера. Покрытие вершин неориентированного графа - это подмножество вершин, которое касается всех ребер.

Вот точный алгоритм, который использует приближение на первом этапе.

Этап 1. Настройка целочисленного линейного программирования для задачи о минимальном покрытии вершин . Известно (или легко показать), что базовое оптимальное решение релаксации линейного программирования является полуцелым (т. Е. Каждая координата равна 0, 1 или 1/2). Такое базовое оптимальное решение может быть найдено с помощью обычного алгоритма полиномиального времени для линейного программирования (или в этом особом случае мы можем сформулировать его как задачу сетевого потока, чтобы мы могли решить его комбинаторно за полиномиальное время). Имея такое базовое оптимальное решение, мы округляем его, чтобы получить реальное решение исходной задачи целочисленного линейного программирования. Пусть S будет соответствующим подмножеством вершин. Хорошо отметить, что S является 2-аппроксимацией данного минимального экземпляра покрытия вершины.

Фаза 2: Найти минимальное покрытие вершин в подграфе, индуцированном S (например, путем исчерпывающего поиска). Теорема Немхаузера и Троттера утверждает, что этот подграф содержит оптимальное решение исходного входного графа. Итак, правильность такого подхода заключается в следующем.

Вы можете обратиться к книге Niedermeier об алгоритмах с фиксированными параметрами для этого алгоритма.

Один пример связан с разложением деревьев и графиками малой ширины дерева .

$B$

$B$$A$

$A$$A$$A$$A$$B$

$B$$A$

$B$$A$$A$$B$

Примером алгоритма аппроксимации, который сходится к точному решению, может быть алгоритм эллипсоида для решения LP - если коэффициенты являются рациональными, то можно вычислить минимальное расстояние между двумя вершинами допустимого многогранника. Теперь алгоритм эллипсоида многократно вычисляет все меньший и меньший эллипозоид, который должен содержать оптимальное решение. Как только эллипозоид станет достаточно маленьким, чтобы содержать только такую ​​единственную вершину, вы по существу нашли оптимальную вершину. Вот почему LP слабо полиномиален.

$k$

Наконец, дальнейшее развитие - множество алгоритмов, которые следуют технике изменения (взять случайную выборку - а затем сделать некоторые исправления, чтобы получить то, что вы хотите) попадают в такую ​​структуру. Один милый пример - алгоритм вычисления медианы с использованием случайной выборки (см. Книгу Мотвани и Рагхавана). Есть много таких примеров - возможно, многие из рандомизированных инкрементальных алгоритмов в вычислительной геометрии попадают в эту структуру.

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

Проблема . Вам дан массив A [1 .. n ], в котором каждый элемент находится на расстоянии не более k позиций от позиции, в которой он был бы, если бы сортировался A.

Например, A [1..7], показанный ниже, может быть входным массивом для k = 2.

Источник проблемы: Algo Muse Archive.