Существует богатая литература и, по крайней мере, одна очень хорошая книга, в которой излагаются известные значения твердости аппроксимации для NP-трудных задач в контексте мультипликативной ошибки (например, 2-аппроксимация для покрытия вершин оптимальна при условии UGC). Это также включает хорошо понятные классы сложности аппроксимации, такие как APX, PTAS и так далее.
Что известно, когда следует учитывать аддитивную ошибку? Поиск в литературе показывает несколько результатов типа верхней границы, особенно для упаковки бина (см., Например, http://www.cs.princeton.edu/courses/archive/spr03/cs594/dpw/lecture2.ps ), но есть более сложная классификация классов сложности или есть причина, почему она не так интересна или актуальна?
В качестве дальнейшего комментария, например, для упаковки бина, насколько я знаю, нет теоретической причины, по которой не удалось найти алгоритм поли времени, который всегда находится в аддитивном расстоянии от оптимального значения 1 (хотя я исправляюсь ). Будет ли такой алгоритм разрушать какие-либо классы сложности или иметь какой-либо другой значительный теоретический эффект?
РЕДАКТИРОВАТЬ: Ключевая фраза, которую я не использовал, это «класс асимптотической аппроксимации» (спасибо, Александр). Кажется, что в этой области есть работа, но она еще не достигла той же стадии зрелости, что и теория классических приближенных классов.
Ответы:
Вопрос несколько открытый, поэтому я не думаю, что на него можно ответить полностью. Это частичный ответ.
Легко заметить, что многие проблемы неинтересны, когда мы рассматриваем аддитивное приближение. Например, традиционно целевой функцией задачи 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
источник
Это частичный ответ
-Каждый кубический рисунок является 4-раскрашиваемым по краю за полиномиальное время, но раскраска по 3-краю является NP-трудной.
источник
В последнее время появились работы по классам асимптотических приближений и их сравнению с классическими аналогами.
Эрик Ян ван Леувен и Ян ван Леувен. Структура полиномиально-временного приближения . Технический отчет UU-CS-2009-034. Декабрь 2009 г.
источник