Теорема об иерархии для отношений аппроксимации?

12

Как хорошо известно, задачи NP-hard оптимизации могут иметь много разных коэффициентов аппроксимации, начиная от PTAS и заканчивая отсутствием аппроксимации ни по одному фактору. Между ними у нас есть различные константы, , и т. Д.p o l y ( n )O(logn)poly(n)

Что известно о наборе возможных соотношений? Можем ли мы доказать какую-либо «иерархию приближений»? Формально, для каких функций и мы можем доказать, что существует проблема с коэффициентом аппроксимации ?g ( n ) f ( n ) α < g ( n )f(n)g(n)f(n)α<g(n)

В случае, если , существует ли проблема с отношением аппроксимации точно ?αα=O(1)α

Джереми Хурвиц
источник
Доказательство такой теоремы скорее всего будет напоминать wisdom.weizmann.ac.il/~oded/p_testHT.html . Учитывая проблему с известной аппроксимацией границей , мы каким-то образом облегчаем задачу, предположительно используя некоторую форму заполнения, чтобы получить проблему с аппроксимацией границей . f ( α )αf(α)
Джереми Хурвиц
1
и p o l y ( n ) не являются константами. O(logn)poly(n)
Тайсон Уильямс
2
@TysonWilliams: я думаю, он имел в виду, что между PTAS и отсутствием приближений есть константы, log, poly (n) и т. Д.
Суреш Венкат
6
Разве вам не нужно исключать тривиальные преобразования, где аппроксимация для минимизации f немедленно является α аппроксимация для минимизацииα ? f
Суреш Венкат
1
Что касается вашего последнего вопроса об α = O (1), тесная граница была показана для многих проблем, таких как упаковка бина, машинное планирование (iris.gmu.edu/~khoffman/papers/set_covering.html)
Gopi

Ответы:

3

Существует иерархия аппроксимации, основные известные примеры: FPTAS EPTAS PTAS APX . Но для неприемлемости есть и NPO-PB .

Существует множество результатов о наборе возможных соотношений, исходя из таких результатов:

EPTAS FPTAS, если P = N P ,P||CmaxP=NP

для определения APX / NPO-PB-сложные проблемы.

Некоторые ссылки:

  • НА ПТАС: М. Сесати и Л. Тревизан. Об эффективности схем аппроксимации полиномиального времени, 1997.
  • На НПОПБ: В. Канн. Сильные нижние оценки аппроксимируемости некоторых задач максимизации полного замыкания НКО

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

Кроме того, как указано в комментариях, жесткая граница, когда , была показана для многих проблем, таких как упаковка бункеров, машинное планирование (см. Iris.gmu.edu/~khoffman/papers/set_covering.html).α=O(1)

Гопи
источник
2

Я все еще думаю, что комментария Суреша под вопросом достаточно, чтобы показать, что любое соотношение возможно. Если вы не уверены в этом, вы можете, например, взглянуть на Булевы проблемы удовлетворения ограничений (CSP).

Фон: Пусть - предикат арности k . Экземпляр Max-CSP (P) находится над n k булевых переменных x 1 , , x n . Литерал - это любая переменная или ее отрицание. Экземпляр состоит из m ограничений, каждая из которых имеет вид P ( λ 1 , , λ k ), где λ iP:{0,1}k{0,1}knkx1,,xnmP(λ1,,λk)λiнекоторые литералы, и цель состоит в том, чтобы найти назначение переменных, которое максимизирует долю удовлетворяет ограничениям. Например, в имеем P ( x 1 , x 2 , x 3 ) = x 1x 2x 3 . Определим р ( Р ) в качестве фракции 2 к возможных входных данных , которые удовлетворяют условию Р (для 3 S A T оно равно 7 / 83SATP(x1,x2,x3)=x1x2x3ρ(P)2kP3SAT7/8). Тривиально аппроксимировать любой Max-CSP (P) коэффициентом тривиально , назначая случайные значения переменным (а затем дерадимизировать, используя метод условных ожиданий). Обратите внимание, что здесь мы имеем соглашение о том, что отношения аппроксимации являются положительными действительными значениями не более 1. Предикат P является устойчивым к аппроксимации (AR), если NP-сложнее решить Max-CSP (P) лучше, чем с помощью коэффициента ρ ( P ) (т. е. ρ ( P ) + ϵ для любого фиксированного ϵ > 0 ).ρ(P)Pρ(P)ρ(P)+ϵϵ>0

ρ(P)Pρ(P)P

Пер Острин и Йохан Хостад, «Случайно поддерживаемые независимость и сопротивление», SIAM Journal on Computing, vol. 40, нет 1, с. 1-27, 2011.

αααρ(P)=α

MCH
источник