Твердость аппроксимации

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

Объем

Трудность аппроксимации дополняет изучение алгоритмов аппроксимации , доказывая для некоторых задач ограничение на факторы, с помощью которых их решение может быть эффективно аппроксимировано. Обычно такие пределы показывают коэффициент аппроксимации, за пределами которого проблема становится NP-трудной , подразумевая, что нахождение полиномиальной аппроксимации для проблемы невозможно, если только NP=P . Однако некоторая сложность результатов аппроксимации основана на других гипотезах, примечательной из которых является гипотеза об уникальных играх .

История

С начала 1970-х годов было известно, что многие задачи оптимизации не могут быть решены за полиномиальное время, если только P = NP , но во многих из этих задач оптимальное решение можно было эффективно аппроксимировать до определенной степени. В 1970-х годах Теофило Ф. Гонсалес и Сартадж Сахни начали исследование сложности аппроксимации, показав, что некоторые задачи оптимизации были NP-трудными даже для аппроксимации с точностью до заданного коэффициента аппроксимации . То есть для этих задач существует такой порог, что любая аппроксимация за полиномиальное время со степенью аппроксимации, превышающей этот порог, может использоваться для решения NP-полных задач за полиномиальное время. ^[1] В начале 1990-х годов, с развитием теории PCP , стало ясно, что многие другие задачи аппроксимации трудно аппроксимировать и что (если только P = NP) многие известные алгоритмы аппроксимации достигают наилучшего возможного коэффициента аппроксимации.

Теория жесткости аппроксимации занимается изучением порога аппроксимации таких задач.

Примеры

Пример NP-сложной задачи оптимизации, которую трудно аппроксимировать, см. в set Cover .

См. также

Теорема PCP

Ссылки

^ Сахни, Сартадж ; Гонсалес, Теофило (1976), « P Задачи -полной аппроксимации», Journal of the ACM , 23 (3): 555–565, doi : 10.1145/321958.321975 , hdl : 10338.dmlcz/103883 , MR 0408313 .

Дальнейшее чтение

Тревизан, Лука (27 июля 2004 г.), Неаппроксимируемость задач комбинаторной оптимизации (PDF)

Внешние ссылки

CSE 533: Теорема PCP и твердость аппроксимации, осень 2005 г. , программа Вашингтонского университета , Венкатесан Гурусвами и Райан О'Доннелл.

[1] Сахни, Сартадж ; Гонсалес, Теофило (1976), « P Задачи -полной аппроксимации», Journal of the ACM , 23 (3): 555–565, doi : 10.1145/321958.321975 , hdl : 10338.dmlcz/103883 , MR 0408313 .

[1]