Твердость аппроксимации - аддитивная ошибка

24

Существует богатая литература и, по крайней мере, одна очень хорошая книга, в которой излагаются известные значения твердости аппроксимации для NP-трудных задач в контексте мультипликативной ошибки (например, 2-аппроксимация для покрытия вершин оптимальна при условии UGC). Это также включает хорошо понятные классы сложности аппроксимации, такие как APX, PTAS и так далее.

Что известно, когда следует учитывать аддитивную ошибку? Поиск в литературе показывает несколько результатов типа верхней границы, особенно для упаковки бина (см., Например, http://www.cs.princeton.edu/courses/archive/spr03/cs594/dpw/lecture2.ps ), но есть более сложная классификация классов сложности или есть причина, почему она не так интересна или актуальна?

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

РЕДАКТИРОВАТЬ: Ключевая фраза, которую я не использовал, это «класс асимптотической аппроксимации» (спасибо, Александр). Кажется, что в этой области есть работа, но она еще не достигла той же стадии зрелости, что и теория классических приближенных классов.

Рафаэль
источник
Какое название книги вы упомянули?
Каролина Солтыс
2
Я не уверен, что это правильно. См. Страницу 2 примечаний, связанных в этом вопросе, в частности теоремы 3 и 4, а также открытую проблему, изложенную чуть ниже теоремы 4. Я упомянул конкретную книгу «Алгоритмы аппроксимации» Виджая Вазирани, которая превосходна.
Рафаэль
Фриз и Каннан ( research.microsoft.com/en-us/um/people/kannan/Papers/… ) дали рандомизированный алгоритм с постоянным временем с аддитивной ошибкой epsilon n ^ k для любой задачи максимального удовлетворения ограничений с ограничениями arity k.
Уоррен Шуди
Я думаю, что упаковка бина с точностью до OPT + 1 полностью соответствует современным знаниям. На самом деле предполагается, что конфигурация LP имеет аддитивную интегральную щель 1 (я считаю, что гипотеза немного дикая, но нет известных контрпримеров).
Сашо Николов

Ответы:

23

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

Легко заметить, что многие проблемы неинтересны, когда мы рассматриваем аддитивное приближение. Например, традиционно целевой функцией задачи Max-3SAT является количество удовлетворенных предложений. В этой формулировке аппроксимация Max-3SAT в пределах аддитивной ошибки O (1) эквивалентна точному решению Max-3SAT просто потому, что целевую функцию можно масштабировать путем многократного копирования входной формулы. Мультипликативная аппроксимация гораздо важнее для задач такого рода.

[Редактировать: В предыдущей редакции я использовал Независимый набор в качестве примера в предыдущем абзаце, но я изменил его на Max-3SAT, потому что Независимый набор не является хорошим примером для иллюстрации разницы между мультипликативным приближением и аддитивным приближением; аппроксимация независимого множества даже в пределах O (1) мультипликативного множителя также является NP-трудной. На самом деле Хастад [Has99] показывает гораздо более сильную неприемлемость для независимого множества.

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

Например, если целевая функция Max-3SAT переопределена как отношение количества удовлетворенных предложений к общему количеству предложений (как это иногда делается), аддитивная аппроксимация становится интересной. В этом случае аддитивная аппроксимация не сложнее, чем мультипликативная аппроксимация в том смысле, что аппроксимация в мультипликативном множителе 1− ε (0 < ε <1) подразумевает аппроксимируемость в пределах аддитивной ошибки ε , поскольку оптимальное значение всегда не более 1.

Интересный факт (который, к сожалению, часто упускается из виду) заключается в том, что многие результаты неприемлемости доказывают NP-полноту некоторых проблем с пропускамичто не следует из простой NP-твердости мультипликативного приближения (см. также Petrank [Pet94] и Goldreich [Gol05, Section 3]). Продолжая пример Max-3SAT, Хостад [Has01] хорошо известен, что трудно аппроксимировать Max-3SAT с постоянным мультипликативным коэффициентом лучше, чем 7/8. Один только этот результат, по-видимому, не означает, что NP-трудно приблизить коэффициентную версию Max-3SAT в пределах постоянной аддитивной погрешности, превышающей некоторый порог. Однако то, что доказывает Хастад [Has01], сильнее простой мультипликативной неприемлемости: он доказывает, что следующая задача обещания является NP-полной для каждой константы 7/8 < s <1:

GAP-3sat сек
Экземпляр : кнф формула φ , где каждое предложение включает в себя ровно три различных переменных.
Да-обещание : φ выполнимо.
Без обещания : ни одно правдивое присвоение не удовлетворяет более чем s части пунктов φ.

Исходя из этого, мы можем сделать вывод, что с точки зрения NP трудно приблизить коэффициент версии Max-3SAT в пределах аддитивной ошибки лучше, чем 1/8. С другой стороны, обычное простое случайное распределение дает приближение в пределах аддитивной ошибки 1/8. Следовательно, результат Хостада [Has01] не только дает оптимальную мультипликативную неприемлемость для этой задачи, но и оптимальную аддитивную неприемлемость. Я полагаю, что существует множество аддитивных результатов недостижимости, подобных этим, которые явно не встречаются в литературе.

Ссылки

[Gol05] Одед Голдрайх. О проблемах обещания (обзор памяти Шимона Эвена [1935-2004]). Электронный коллоквиум по вычислительной сложности , отчет TR05-018, февраль 2005 г. http://eccc.hpi-web.de/report/2005/018/

[Has99] Йохан Хостад. Клику трудно аппроксимировать в пределах n 1 - ε . Acta Mathematica , 182 (1): 105–142, март 1999 г. http://www.springerlink.com/content/m68h3576646ll648/

[Has01] Йохан Хостад. Некоторые оптимальные результаты неприемлемости. Журнал ACM , 48 (4): 798–859, июль 2001 г. http://doi.acm.org/10.1145/502090.502098

[Pet94] Эрез Петранк. Твердость аппроксимации: Разрыв местоположения. Вычислительная сложность , 4 (2): 133–157, апрель 1994 г. http://dx.doi.org/10.1007/BF01202286

Цуёси Ито
источник
3
В качестве другого примера, я думаю, было бы вполне естественно сформулировать задачу максимального разреза, чтобы мы максимизировали долю краев в разрезе. Опять же, мы имеем как положительные, так и отрицательные результаты для аддитивного приближения.
Юкка Суомела
1
@Jukka, не могли бы вы дать ссылку на эту формулировку Max-cut?
Мухаммед Аль-Туркистани
1
Большое спасибо. Похоже, что это область, нуждающаяся хотя бы в обследовании. Насколько я вижу, в зоопарке сложности даже не упоминаются классы приближения аддитивных ошибок (хотя он настолько большой, что я, возможно, что-то пропустил).
Рафаэль
@ Рафаэль: Я бы нашел опрос (или указатель на него) довольно полезным. Насколько я могу судить, классы алгоритмов аппроксимации в последний раз обследовались около десяти лет назад, и я нашел представление далеко не ясным.
Андрас Саламон
6

Это частичный ответ

ABSABS

NP

-Каждый кубический рисунок является 4-раскрашиваемым по краю за полиномиальное время, но раскраска по 3-краю является NP-трудной.

ABSP=Nп

Мухаммед Аль-Туркистани
источник
Спасибо. Я заметил, что ABS не указан в зоопарке сложности qwiki.stanford.edu/index.php/Complexity_Zoo:A . У вас есть ссылка на это?
Рафаэль
Проверьте эталонную, citeseerx.ist.psu.edu/viewdoc/...
Мохаммад Аль-Turkistany
Правильно ли я считаю, что название ABS для класса сложности - это то, что вы только что придумали, или есть ссылка на него? Ссылка, которую вы разместили, похоже, не упоминает об этом.
Рафаэль
@ Рафаэль, нет, я не чеканил название АБС, я его где-то давно читал.
Мухаммед Аль-Туркистани
6

В последнее время появились работы по классам асимптотических приближений и их сравнению с классическими аналогами.

Эрик Ян ван Леувен и Ян ван Леувен. Структура полиномиально-временного приближения . Технический отчет UU-CS-2009-034. Декабрь 2009 г.

Александр бондаренко
источник