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

11

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

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

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

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

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

sdcvvc
источник
Кросспост из математики SE
sdcvvc
Не могли бы вы уточнить, что вы подразумеваете под и весом ? SBAS
Ёсио Окамото
Это неформально, для конкретности: - это задачи поиска , - это задача оптимизации (поэтому решения имеют некоторый вес), а - композиция отношений. A B AA,BABA
sdcvvc
Ответы будут сборником. Итак, я думаю, что было бы более уместно сделать это вики-сообществом.
Ёсио Окамото
Добавление тега большого списка достаточно, нет необходимости делать его вики-сообществом IMHO.
Гопи

Ответы:

12

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

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

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

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

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

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

Ёсио Окамото
источник
11

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

B

BA

AAAAB


BA

BAAB

Юкка Суомела
источник
В то время как пример ширины дерева работает в принципе, его будет трудно выполнить на практике, потому что очень трудно точно аппроксимировать ширину дерева (так как вы можете приблизить клику)
Суреш Венкат
8

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

k

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

Сариэль Хар-Пелед
источник
4

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

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

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

Разработайте алгоритм для сортировки массива за O ( n log k ), предполагая, что k неизвестно.

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

Jagadish
источник