Алгоритм приближения - Approximation algorithm

В информатике и исследование операций , алгоритмы аппроксимации являются эффективными алгоритмами , которые находят приближенный решения задач оптимизации (в частности , NP-трудных задачах) с доказательными гарантиями на расстоянии возвращенного решения оптимального. Алгоритмы приближения естественным образом возникают в области теоретической информатики как следствие широко распространенной гипотезы P ≠ NP . Согласно этой гипотезе, широкий класс задач оптимизации не может быть решен точно за полиномиальное время . Поэтому область аппроксимационных алгоритмов пытается понять, насколько точно можно аппроксимировать оптимальные решения таких задач за полиномиальное время. В подавляющем большинстве случаев гарантия таких алгоритмов является мультипликативной, выраженной как коэффициент аппроксимации или коэффициент аппроксимации, т.е. оптимальное решение всегда гарантированно находится в пределах (заранее определенного) мультипликативного коэффициента возвращенного решения. Однако существует также множество алгоритмов аппроксимации, которые обеспечивают дополнительную гарантию качества возвращаемого решения. Ярким примером алгоритма приближения, который обеспечивает оба, является классический алгоритм приближения Ленстры , Шмойса и Тардоса для планирования на несвязанных параллельных машинах .

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

Теоретическая информатика проявляет большой интерес к лучшему пониманию пределов, до которых мы можем приблизиться к некоторым известным задачам оптимизации. Например, одним из давних открытых вопросов в информатике является определение того, существует ли алгоритм, который превосходит алгоритм 1,5 аппроксимации Христофидеса для метрической задачи коммивояжера . Желание понять сложные проблемы оптимизации с точки зрения аппроксимируемости мотивировано открытием удивительных математических связей и широко применимых методов для разработки алгоритмов для сложных задач оптимизации. Одним из хорошо известных примеров первого является алгоритм Гоеманса – Вильямсона для максимального разреза , который решает теоретико-графическую задачу с использованием геометрии большой размерности.

Вступление

Простой пример алгоритма аппроксимации - это алгоритм для задачи о минимальном покрытии вершин , где цель состоит в том, чтобы выбрать наименьшее множество вершин, такое, чтобы каждое ребро во входном графе содержало по крайней мере одну выбранную вершину. Один из способов найти покрытие вершины - повторить следующий процесс: найти непокрытое ребро, добавить оба его конца к покрытию и удалить все ребра, инцидентные любой вершине из графа. Поскольку любое вершинное покрытие входного графа должно использовать отдельную вершину для покрытия каждого ребра, которое было рассмотрено в процессе (поскольку оно формирует соответствие ), полученное вершинное покрытие, следовательно, не более чем в два раза больше оптимального. Другими словами, это алгоритм аппроксимации с постоянным коэффициентом с коэффициентом аппроксимации 2. Согласно недавней гипотезе об уникальных играх , этот коэффициент является даже наилучшим из возможных.

NP-сложные задачи сильно различаются по аппроксимируемости; некоторые из них, такие как задача о рюкзаке , могут быть аппроксимированы в пределах мультипликативного коэффициента для любого фиксированного значения и, следовательно, дают решения, сколь угодно близкие к оптимальным (такое семейство алгоритмов аппроксимации называется схемой аппроксимации с полиномиальным временем или PTAS). Другие невозможно аппроксимировать в рамках какого-либо постоянного или даже полиномиального множителя, если только P = NP , как в случае задачи о максимальной клике . Таким образом, важным преимуществом изучения аппроксимационных алгоритмов является детальная классификация сложности различных NP-сложных задач, выходящая за рамки той, которую дает теория NP-полноты . Другими словами, хотя NP-полные задачи могут быть эквивалентны (при полиномиальном сокращении времени) друг другу с точки зрения точных решений, соответствующие задачи оптимизации ведут себя по-разному с точки зрения приближенных решений. ${\ displaystyle 1+ \ epsilon}$${\ displaystyle \ epsilon> 0}$

Методы проектирования алгоритмов

К настоящему времени существует несколько установленных методов для разработки алгоритмов аппроксимации. К ним относятся следующие.

1. Жадный алгоритм
2. Локальный поиск
3. Перечисление и динамическое программирование
4. Решение релаксации выпуклого программирования для получения дробного решения. Затем преобразование этого дробного решения в допустимое решение путем некоторого соответствующего округления. К популярным видам отдыха можно отнести следующие.
   • Расслабления в линейном программировании
   • Полуопределенное программирование послабление
5. Первобытно-дуальные методы
6. Двойной фитинг
7. Вложение проблемы в некоторую метрику, а затем решение проблемы на метрике. Это также известно как метрическое вложение.
8. Случайная выборка и использование случайности в целом в сочетании с вышеуказанными методами.

Апостериорные гарантии

Хотя алгоритмы аппроксимации всегда обеспечивают априорную гарантию наихудшего случая (будь то аддитивная или мультипликативная), в некоторых случаях они также предоставляют апостериорную гарантию, которая часто намного лучше. Это часто случается с алгоритмами, которые работают, решая выпуклую релаксацию задачи оптимизации на заданном входе. Например, существует другой алгоритм аппроксимации минимального покрытия вершины, который решает релаксацию линейного программирования, чтобы найти покрытие вершины, которое не более чем в два раза превышает значение релаксации. Поскольку величина релаксации никогда не превышает размер оптимального покрытия вершин, это дает другой алгоритм с двумя приближениями. Хотя это похоже на априорную гарантию предыдущего алгоритма аппроксимации, гарантия последнего может быть намного лучше (действительно, когда значение LP-релаксации далеко от размера оптимального вершинного покрытия).

Твердость приближения

Приближенные алгоритмы как область исследований тесно связаны и проинформировано теории inapproximability где несуществование эффективных алгоритмов с определенными коэффициентами аппроксимации доказано (обусловлено широко распространенное мнением гипотез , такие как гипотеза P ≠ NP) с помощью сокращений . В случае метрической задачи коммивояжера наиболее известный результат о неприближаемости исключает алгоритмы с коэффициентом аппроксимации менее 123/122 ≈ 1,008196, если только P = NP, Karpinski, Lampis, Schmied. В сочетании со знанием существования алгоритма аппроксимации 1.5 Кристофидеса это говорит нам о том, что порог аппроксимации для метрического коммивояжера (если он существует) находится где-то между 123/122 и 1.5.

Хотя с 1970-х годов были доказаны результаты о несовместимости, такие результаты были получены специальными методами, и в то время не было никакого систематического понимания. Только после того, как в 1990 г. был получен результат Фейге, Гольдвассера, Ловаса, Сафры и Сегеди о неапроксимируемости независимого множества и знаменитая теорема PCP , были открыты современные инструменты для доказательства результатов о несовместимости. Теорема PCP, например, показывает, что алгоритмы аппроксимации Джонсона 1974 г. для Max SAT , покрытия множества , независимого множества и раскраски все достигают оптимального отношения аппроксимации, предполагая, что P ≠ NP.

Практичность

Не все алгоритмы аппроксимации подходят для непосредственного практического применения. Некоторые из них включают решение нетривиального линейного программирования / полуопределенных релаксаций (которые сами могут вызывать алгоритм эллипсоида ), сложных структур данных или сложных алгоритмических методов, что приводит к сложным проблемам реализации или повышению производительности по времени (по сравнению с точными алгоритмами) только на непрактично больших входных данных. . Помимо вопросов реализации и времени выполнения, гарантии, предоставляемые алгоритмами аппроксимации, сами по себе могут быть недостаточно сильными, чтобы оправдать их рассмотрение на практике. Несмотря на то, что их нельзя использовать «из коробки» в практических приложениях, идеи и идеи, лежащие в основе разработки таких алгоритмов, часто могут быть включены в практические алгоритмы другими способами. Таким образом, изучение даже очень дорогих алгоритмов не является полностью теоретическим занятием, поскольку может дать ценную информацию.

В других случаях, даже если первоначальные результаты представляют чисто теоретический интерес, со временем, с улучшенным пониманием, алгоритмы могут быть усовершенствованы, чтобы стать более практичными. Одним из таких примеров является начальный PTAS для евклидовой TSP, разработанный Сандживом Аророй (и независимо Джозефом Митчеллом ), у которого было недопустимое время работы для приближения. Тем не менее, в течение года эти идеи были включены в алгоритм почти линейного времени для любой постоянной . ${\ Displaystyle п ^ {О (1 / \ эпсилон)}}$${\ displaystyle 1+ \ epsilon}$${\ Displaystyle О (п \ журнал п)}$${\ displaystyle \ epsilon> 0}$

Гарантии работоспособности

Для некоторых алгоритмов аппроксимации можно доказать определенные свойства приближения к оптимальному результату. Например, алгоритм A ρ- аппроксимации определяется как алгоритм, для которого было доказано, что значение / стоимость, f ( x ), приближенного решения A ( x ) для экземпляра x не будет больше (или меньше, в зависимости от ситуации), чем коэффициент ρ, умноженный на значение OPT оптимального решения.

${\ displaystyle {\ begin {case} \ mathrm {OPT} \ leq f (x) \ leq \ rho \ mathrm {OPT}, \ qquad {\ mbox {if}} \ rho> 1; \\\ rho \ mathrm {OPT} \ leq f (x) \ leq \ mathrm {OPT}, \ qquad {\ mbox {if}} \ rho <1. \ end {cases}}}$

Коэффициент ρ называется относительной гарантией производительности . Алгоритм аппроксимации имеет абсолютную гарантию производительности или ограниченную ошибку c , если для каждого экземпляра x было доказано, что

${\ displaystyle (\ mathrm {OPT} -c) \ leq f (x) \ leq (\ mathrm {OPT} + c).}$

Аналогичным образом , гарантия исполнения , Р ( х, у ), из раствора у к экземпляру х определяется как

${\ displaystyle R (x, y) = \ max \ left ({\ frac {OPT} {f (y)}}, {\ frac {f (y)} {OPT}} \ right),}$

где f ( y ) - стоимость / стоимость решения y для экземпляра x . Ясно, что гарантия производительности больше или равна 1 и равна 1 тогда и только тогда, когда y является оптимальным решением. Если алгоритм A гарантирует возврат решений с гарантией производительности при большем г ( п ), то называется быть г ( п ) алгоритмом -аппроксимации и имеет отношение аппроксимации по г ( п ). Кроме того, проблема с г ( п ) -аппроксимация алгоритм назовет г ( п ) - аппроксимируемо или иметь коэффициент аппроксимации г ( п ).

Для задач минимизации две разные гарантии обеспечивают один и тот же результат, а для задач максимизации относительная гарантия производительности ρ эквивалентна гарантии производительности . В литературе используются оба определения, но ясно, какое определение используется, поскольку для задач максимизации, как ρ ≤ 1, а r ≥ 1. ${\ Displaystyle г = \ ро ^ {- 1}}$

Абсолютная гарантия производительности некоторого приближение алгоритм А , где х относится к экземпляру проблемы, и где является гарантией исполнения А по й (т.е. ρ, например , проблемы х ) является: ${\ Displaystyle \ mathrm {P} _ {A}}$${\ Displaystyle R_ {A} (х)}$

${\ displaystyle \ mathrm {P} _ {A} = \ inf \ {r \ geq 1 \ mid R_ {A} (x) \ leq r, \ forall x \}.}$

Другими словами, это наибольшая граница отношения приближения r , которую можно увидеть по всем возможным случаям проблемы. Аналогичным образом асимптотический коэффициент производительности равен: ${\ Displaystyle \ mathrm {P} _ {A}}$ ${\ Displaystyle R_ {A} ^ {\ infty}}$

${\ Displaystyle R_ {A} ^ {\ infty} = \ inf \ {r \ geq 1 \ mid \ exists n \ in \ mathbb {Z} ^ {+}, R_ {A} (x) \ leq r, \ для всех x, | x | \ geq n \}.}$

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

Гарантии работоспособности

	r -приблизительно	ρ -прибл.	отн. ошибка	отн. ошибка	норма. отн. ошибка	абс. ошибка
Максимум: ${\ Displaystyle е (х) \ geq}$	${\ displaystyle r ^ {- 1} \ mathrm {OPT}}$	${\ displaystyle \ rho \ mathrm {OPT}}$	${\ displaystyle (1-c) \ mathrm {OPT}}$	${\ displaystyle (1-c) \ mathrm {OPT}}$	${\ displaystyle (1-c) \ mathrm {OPT} + c \ mathrm {НАИЛУЧШИЙ}}$	${\ displaystyle \ mathrm {OPT} -c}$
мин: ${\ Displaystyle е (х) \ leq}$	${\ displaystyle r \ mathrm {OPT}}$	${\ displaystyle \ rho \ mathrm {OPT}}$	${\ Displaystyle (1 + с) \ mathrm {OPT}}$	${\ Displaystyle (1-с) ^ {- 1} \ mathrm {OPT}}$	${\ displaystyle (1-c) ^ {- 1} \ mathrm {OPT} + c \ mathrm {НАИЛУЧШИЙ}}$	${\ displaystyle \ mathrm {OPT} + c}$

Условия использования Epsilon

В литературе коэффициент аппроксимации для задачи максимизации (минимизации) c - ϵ (min: c + ϵ) означает, что алгоритм имеет коэффициент аппроксимации c ∓ ϵ для произвольного ϵ> 0, но это отношение не имеет (или не может) быть показано для ϵ = 0. Примером этого является оптимальная неприближаемость - отсутствие приближения - соотношение 7/8 + ϵ для выполнимых экземпляров MAX-3SAT, созданное Йоханом Хастадом . Как упоминалось ранее, когда c = 1, говорят, что задача имеет схему аппроксимации за полиномиальное время .

-Член может появиться, когда алгоритм приближения вводит мультипликативную ошибку и постоянную ошибку, в то время как минимальный оптимум экземпляров размера n стремится к бесконечности, как это делает n . В этом случае коэффициент аппроксимации равен c ∓ k / OPT = c ∓ o (1) для некоторых констант c и k . Учитывая произвольное ε> 0, можно выбрать достаточно большой N , такие , что термин к / OPT <ε для любого п ^ N . Для каждого фиксированного ϵ экземпляры размера n <N могут быть решены грубой силой, тем самым показывая коэффициент аппроксимации - наличие алгоритмов аппроксимации с гарантией - c ∓ ϵ для каждого> 0.

Смотрите также

• Анализ доминирования рассматривает гарантии с точки зрения ранга вычисленного решения.
• PTAS - тип алгоритма аппроксимации, который принимает коэффициент аппроксимации в качестве параметра
• APX - это класс задач с некоторым алгоритмом аппроксимации с постоянным коэффициентом.
• Приведение с сохранением приближения
• Точный алгоритм

Цитаты

использованная литература

• Вазирани, Виджай В. (2003). Аппроксимационные алгоритмы . Берлин: Springer. ISBN 978-3-540-65367-7.
• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN  0-262-03293-7 . Глава 35: Алгоритмы приближения, стр. 1022–1056.
• Дорит С. Хохбаум , изд. Аппроксимационные алгоритмы для NP-сложных задач , PWS Publishing Company, 1997. ISBN  0-534-94968-1 . Глава 9: Различные понятия приближения: хорошее, лучшее, лучшее и т. Д.
• Уильямсон, Дэвид П .; Шмойс, Дэвид Б. (26 апреля 2011 г.), Разработка алгоритмов аппроксимации , Cambridge University Press , ISBN 978-0521195270

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

• Пьерлуиджи Крещенци, Вигго Канн, Магнус Халльдорссон, Марек Карпински и Герхард Вегингер , Сборник задач оптимизации NP .