В информатике и исследовании операций алгоритмы аппроксимации — это эффективные алгоритмы , которые находят приближенные решения задач оптимизации (в частности, NP-трудных задач) с доказуемыми гарантиями расстояния возвращаемого решения до оптимального. [1] Аппроксимационные алгоритмы естественным образом возникают в области теоретической информатики как следствие широко распространенной гипотезы P ≠ NP . Согласно этой гипотезе, широкий класс задач оптимизации не может быть решен точно за полиномиальное время . Поэтому область аппроксимирующих алгоритмов пытается понять, насколько точно можно аппроксимировать оптимальные решения таких задач за полиномиальное время. В подавляющем большинстве случаев гарантия таких алгоритмов является мультипликативной, выраженной как коэффициент аппроксимации или коэффициент аппроксимации, т.е. оптимальное решение всегда гарантированно находится в пределах (заранее определенного) мультипликативного коэффициента возвращаемого решения. Однако существует также множество алгоритмов аппроксимации, которые обеспечивают аддитивную гарантию качества возвращаемого решения. Ярким примером алгоритма аппроксимации, который обеспечивает и то, и другое , является классический алгоритм аппроксимации Ленстры , Шмойса и Тардоса [2] для планирования на несвязанных параллельных машинах.
Разработка и анализ алгоритмов аппроксимации в решающей степени включает в себя математическое доказательство , подтверждающее качество возвращаемых решений в худшем случае. [1] Это отличает их от эвристик , таких как отжиг или генетические алгоритмы , которые находят достаточно хорошие решения на некоторых входных данных, но не дают с самого начала четкого указания на то, когда они могут добиться успеха или потерпеть неудачу.
Существует широкий интерес к теоретической информатике , чтобы лучше понять пределы, до которых мы можем приблизиться к некоторым известным задачам оптимизации. Например, одним из давних открытых вопросов в информатике является определение того, существует ли алгоритм, который превосходит 2-приближение для задачи Штайнера Фореста, предложенное Агравалом и др. [3] Желание понять сложные задачи оптимизации с точки зрения аппроксимации мотивировано открытием удивительных математических связей и широко применимых методов разработки алгоритмов для решения сложных задач оптимизации. Одним из хорошо известных примеров первого является алгоритм Гоеманса-Вильямсона для максимального сечения , который решает задачу теории графов с использованием многомерной геометрии. [4]
Простым примером алгоритма аппроксимации является задача о минимальном покрытии вершин , цель которой состоит в том, чтобы выбрать наименьший набор вершин так, чтобы каждое ребро во входном графе содержало хотя бы одну выбранную вершину. Один из способов найти вершинное покрытие — повторить следующий процесс: найти непокрытое ребро, добавить обе его конечные точки в покрытие и удалить из графа все ребра, инцидентные любой вершине. Поскольку любое вершинное покрытие входного графа должно использовать отдельную вершину для покрытия каждого ребра, которое рассматривалось в процессе (поскольку оно образует паросочетание ) , полученное вершинное покрытие, следовательно, не более чем в два раза больше оптимального. Другими словами, это алгоритм аппроксимации с постоянным коэффициентом с коэффициентом аппроксимации 2. Согласно недавней гипотезе об уникальных играх , этот коэффициент даже является наилучшим из возможных. [5]
NP-трудные задачи сильно различаются по своей аппроксимируемости; некоторые, такие как задача о рюкзаке , могут быть аппроксимированы в пределах мультипликативного коэффициента при любом фиксированном и, следовательно, дают решения, сколь угодно близкие к оптимальному (такое семейство алгоритмов аппроксимации называется схемой аппроксимации с полиномиальным временем или PTAS). Другие невозможно аппроксимировать в пределах какого-либо постоянного или даже полиномиального множителя, если только P = NP , как в случае задачи о максимальной клике . Таким образом, важным преимуществом изучения аппроксимационных алгоритмов является детальная классификация сложности различных NP-трудных задач, выходящая за рамки той, которую дает теория NP-полноты . Другими словами, хотя NP-полные задачи могут быть эквивалентны (при полиномиальном сокращении времени) друг другу с точки зрения точных решений, соответствующие задачи оптимизации ведут себя совсем по-другому с точки зрения приближенных решений.
К настоящему времени существует несколько устоявшихся методов разработки алгоритмов аппроксимации. К ним относятся следующие.
Хотя алгоритмы аппроксимации всегда обеспечивают априорную гарантию наихудшего случая (будь то аддитивную или мультипликативную), в некоторых случаях они также предоставляют апостериорную гарантию, которая часто намного лучше. Это часто относится к алгоритмам, которые работают путем решения выпуклой релаксации задачи оптимизации на заданных входных данных. Например, существует другой алгоритм аппроксимации минимального вершинного покрытия, который решает задачу релаксации линейного программирования и находит вершинное покрытие, которое не более чем в два раза превышает значение релаксации. Поскольку значение релаксации никогда не превышает размера оптимального вершинного покрытия, это дает еще один алгоритм 2-приближения. Хотя это похоже на априорную гарантию предыдущего алгоритма аппроксимации, гарантия последнего может быть намного лучше (действительно, когда значение LP-релаксации далеко от размера оптимального вершинного покрытия).
Алгоритмы аппроксимации как область исследований тесно связаны с теорией неаппроксимируемости и основаны на ней, где отсутствие эффективных алгоритмов с определенными коэффициентами аппроксимации доказывается (при условии широко распространенных гипотез, таких как гипотеза P ≠ NP) посредством редукций . В случае метрической задачи коммивояжера наиболее известный результат о неаппроксимируемости исключает алгоритмы с коэффициентом аппроксимации менее 123/122 ≈ 1,008196, если только P = NP, Карпински, Лампис, Шмид. [6] В сочетании со знанием существования алгоритма аппроксимации Кристофидеса 1,5 это говорит нам о том, что порог аппроксимируемости для метрического коммивояжера (если он существует) находится где-то между 123/122 и 1,5.
Хотя результаты о неаппроксимируемости были доказаны с 1970-х годов, такие результаты были получены специальными средствами, и в то время не было никакого систематического понимания. Только после получения в 1990 году результата Фейджа, Гольдвассера, Ловаса, Сафры и Сегеди о неаппроксимируемости независимого множества [7] и знаменитой теоремы PCP [8] были открыты современные инструменты для доказательства результатов о неаппроксимируемости . Теорема PCP, например, показывает, что алгоритмы аппроксимации Джонсона 1974 года для Max SAT , покрытия множества , независимого множества и раскраски достигают оптимального коэффициента аппроксимации, предполагая P ≠ NP. [9]
Не все алгоритмы аппроксимации пригодны для прямого практического применения. Некоторые из них включают решение нетривиального линейного программирования / полуопределенных релаксаций (которые сами по себе могут вызывать алгоритм эллипсоида ), сложные структуры данных или сложные алгоритмические методы, что приводит к сложным проблемам реализации или улучшению производительности времени выполнения (по сравнению с точными алгоритмами) только на непрактично больших входных данных. . Если оставить в стороне проблемы реализации и времени выполнения, гарантии, обеспечиваемые алгоритмами аппроксимации, сами по себе могут быть недостаточно сильными, чтобы оправдать их рассмотрение на практике. Несмотря на невозможность использования «из коробки» в практических приложениях, идеи и идеи, лежащие в основе разработки таких алгоритмов, часто могут быть включены в практические алгоритмы другими способами. Таким образом, изучение даже очень дорогих алгоритмов не является полностью теоретическим занятием, поскольку они могут дать ценную информацию.
В других случаях, даже если первоначальные результаты представляют чисто теоретический интерес, со временем, по мере улучшения понимания, алгоритмы могут быть усовершенствованы и стать более практичными. Одним из таких примеров является первоначальный PTAS для евклидовой TSP, написанный Сандживом Аророй (и независимо Джозефом Митчеллом ), время работы которого для аппроксимации было непомерно большим. [10] Тем не менее, в течение года эти идеи были включены в алгоритм почти линейного времени для любой константы . [11]
Для некоторых алгоритмов аппроксимации можно доказать определенные свойства аппроксимации оптимального результата. Например, алгоритм ρ -аппроксимации A определяется как алгоритм, для которого было доказано, что значение/стоимость f ( x ) приближенного решения A ( x ) для экземпляра x не будет больше (или меньше, в зависимости от ситуации), чем значение OPT, умноженное на ρ , оптимального решения.
Коэффициент ρ называется относительной гарантией производительности . Алгоритм аппроксимации имеет абсолютную гарантию производительности или ограниченную ошибку c , если для каждого экземпляра x доказано, что
Аналогично, гарантия производительности R ( x,y ) решения y для экземпляра x определяется как
где f ( y ) — значение/стоимость решения y для экземпляра x . Очевидно, что гарантия производительности больше или равна 1 и равна 1 тогда и только тогда, когда y является оптимальным решением. Если алгоритм A гарантирует возврат решений с гарантией производительности не более r ( n ), то A называется алгоритмом r ( n )-аппроксимации и имеет коэффициент аппроксимации r ( n ). Аналогично, задача с алгоритмом r ( n )-аппроксимации называется r ( n ) -аппроксимируемой или имеет коэффициент аппроксимации r ( n ). [12] [13]
Для задач минимизации две разные гарантии дают один и тот же результат, а для задач максимизации относительная гарантия производительности ρ эквивалентна гарантии производительности . В литературе распространены оба определения, но ясно, какое определение используется, поскольку для задач максимизации ρ ≤ 1, а r ≥ 1.
Абсолютная гарантия производительности некоторого алгоритма аппроксимации A , где x относится к экземпляру проблемы, а где — гарантия производительности A для x (т. е. ρ для экземпляра проблемы x ), равна:
То есть это наибольшая граница коэффициента аппроксимации r , которую можно увидеть во всех возможных случаях задачи. Аналогично, асимптотический коэффициент производительности :
То есть это то же самое, что и абсолютный коэффициент производительности , с нижней границей n размера экземпляров проблемы. Эти два типа отношений используются потому, что существуют алгоритмы, в которых разница между ними значительна.
В литературе коэффициент аппроксимации для задачи максимизации (минимизации) c - ϵ (мин: c + ϵ) означает, что алгоритм имеет коэффициент аппроксимации c ∓ ϵ для произвольного ϵ > 0, но это отношение не имеет (или не может быть показано для ϵ = 0. Примером этого является оптимальная неаппроксимируемость — отсутствие аппроксимации — соотношение 7/8 + ϵ для выполнимых экземпляров MAX-3SAT из-за Йохана Хостада . [14] Как упоминалось ранее, когда c = 1, говорят, что задача имеет схему аппроксимации с полиномиальным временем .
ϵ-термин может появиться, когда алгоритм аппроксимации вводит мультипликативную ошибку и постоянную ошибку, в то время как минимальный оптимум экземпляров размера n стремится к бесконечности, как это делает n . В этом случае коэффициент аппроксимации равен c ∓ k / OPT = c ∓ o(1) для некоторых констант c и k . Учитывая произвольное ϵ > 0, можно выбрать достаточно большое N такое, чтобы член k /OPT < ϵ для каждого n ≥ N. Для каждого фиксированного ϵ экземпляры размера n < N можно решить методом грубой силы, тем самым показывая коэффициент аппроксимации — существование алгоритмов аппроксимации с гарантией — c ∓ ϵ для каждого ϵ > 0.
{{cite book}}
: CS1 maint: multiple names: authors list (link)