Твердость приближения - Hardness of approximation
В информатике , твердость приближения является полем, изучающая алгоритмическая сложность нахождения вблизи оптимального решения задач оптимизации .
Объем
Трудность аппроксимации дополняет изучение алгоритмов аппроксимации , доказывая для некоторых задач ограничение на факторы, с помощью которых их решение может быть эффективно аппроксимировано. Обычно такие ограничения показывают коэффициент приближения , после которого проблема становится NP-трудной , подразумевая , что нахождение полиномиальное время приближения для задачи невозможно , если NP = P . Однако некоторая сложность результатов аппроксимации основана на других гипотезах, среди которых стоит выделить гипотезу об уникальных играх .
История
С начала 1970-х годов было известно, что многие задачи оптимизации не могут быть решены за полиномиальное время, если P = NP , но во многих из этих задач оптимальное решение может быть эффективно аппроксимировано до определенной степени. В 1970-х годах Теофило Ф. Гонсалес и Сартадж Сахни начали изучение точности аппроксимации, показав, что некоторые задачи оптимизации NP-трудны даже для аппроксимации с точностью до заданного отношения аппроксимации . То есть для этих задач существует порог, такой, что любое приближение за полиномиальное время с коэффициентом приближения, превышающим этот порог, может быть использовано для решения NP-полных задач за полиномиальное время. В начале 1990-х, с развитием теории PCP , стало ясно, что многие другие задачи аппроксимации трудно аппроксимировать и что (если P = NP) многие известные алгоритмы аппроксимации достигают наилучшего возможного отношения аппроксимации.
Трудность теории приближений связана с изучением порога приближения таких задач.
Примеры
Для примера NP-сложной задачи оптимизации, которую трудно аппроксимировать, см. Обложку набора .
Смотрите также
Ссылки
дальнейшее чтение
- Тревизан, Лука (27 июля 2004 г.), Непроксимируемость задач комбинаторной оптимизации (PDF)
внешние ссылки
- CSE 533: Теорема PCP и твердость приближения, осень 2005 г. , программа Вашингтонского университета , Венкатесан Гурусвами и Райан О'Доннелл