Алгоритм аппроксимации

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

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

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

• 1 Введение
• 2 Методы разработки алгоритмов
• 3 Апостериорные гарантии
• 4 Твердость приближения
• 5 Практичность
• 6 Гарантии производительности
• 7 Термины Epsilon
• 8 См. Также
• 9 Цитаты
• 10 Ссылки
• 11 Внешние ссылки

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

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

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

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

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

Алгоритмы аппроксимации как область исследований тесно связаны с теорией аппроксимации и опираются на нее, где доказано отсутствие эффективных алгоритмов с определенными коэффициентами аппроксимации (обусловлено широко распространенными гипотезами, такими как гипотеза 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, сделанный Санджив Арора (и независимо от Джозеф Митчелл ), у которого было недопустимое время выполнения $n\; O\; (1\; /\; ϵ)\; \{\backslash \; displaystyle\; n\; ^\; \{O\; (1\; /\; \backslash \; epsilon)\}\}$для приближения $1\; +\; ϵ\; \{\backslash \; displaystyle\; 1+\; \backslash \; epsilon\}$. Тем не менее, в течение года эти идеи были включены в алгоритм почти линейного времени $O\; (n\; log\; \; n)\; \{\backslash \; displaystyle\; O\; (n\; \backslash \; log\; n)\}$для любой константы $ϵ>0\; \{\backslash \; displaystyle\; \backslash \; epsilon>0\}$.

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

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

$(O\; P\; T\; -\; c)\; \le \; f\; (x)\; \le \; (O\; P\; T\; +\; c).\; \{\backslash \; displaystyle\; (\backslash \; mathrm\; \{OPT\}\; -c)\; \backslash \; leq\; f\; (x)\; \backslash \; leq\; (\backslash \; mathrm\; \{OPT\}\; +\; c).\}$

Аналогичным образом, гарантия производительности R (x, y) решения y к экземпляру x определяется как

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

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

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

Гарантия абсолютной производительности $PA\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{P\}\; \_\; \{A\}\}$некоторого алгоритма аппроксимации A, где x относится к экземпляру проблемы, а где $RA\; (x)\; \{\backslash \; displaystyle\; R\_\; \{A\}\; (x)\}$- гарантия производительности A на x (т.е. ρ для экземпляра задачи x):

$PA\; =\; inf\; \{r\; \ge \; 1\; \mid \; RA\; (x)\; \le \; r,\; \forall \; x\}.\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{P\}\; \_\; \{A\}\; =\; \backslash \; inf\; \backslash \; \{r\; \backslash \; geq\; 1\; \backslash \; mid\; R\_\; \{A\}\; (x)\; \backslash \; leq\; r,\; \backslash \; forall\; x\; \backslash \}.\}$

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

$RA\; \infty \; =\; inf\; \{r\; \ge \; 1\; \mid \; \exists \; n\; \in \; Z\; +,\; RA\; (x)\; \le \; r,\; \forall \; x,\; |\; х\; |\; \ge \; n\}.\; \{\backslash \; Displaystyle\; R\_\; \{A\}\; ^\; \{\backslash \; infty\}\; =\; \backslash \; inf\; \backslash \; \{r\; \backslash \; geq\; 1\; \backslash \; mid\; \backslash \; exists\; n\; \backslash \; in\; \backslash \; mathbb\; \{Z\}\; ^\; \{+\},\; R\_\; \{A\}\; (x)\; \backslash \; leq\; r,\; \backslash \; forall\; x,\; |\; x\; |\; \backslash \; geq\; n\; \backslash \}.\}$

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

Гарантия качества работы

	r-прибл.	ρ-прибл	отн. ошибка	отн. погрешность	норм. отн. ошибка	абс. ошибка
макс.: $f\; (x)\; \ge \; \{\backslash \; displaystyle\; f\; (x)\; \backslash \; geq\}$	$r\; -\; 1\; OPT\; \{\backslash \; displaystyle\; r\; ^\; \{-\; 1\}\; \backslash \; mathrm\; \{OPT\}\}$	$\rho \; OPT\; \{\backslash \; displaystyle\; \backslash \; rho\; \backslash \; mathrm\; \{OPT\}\}$	$(1\; -\; c)\; OPT\; \{\backslash \; displaystyle\; (1-c)\; \backslash \; mathrm\; \{OPT\}\}$	$(1\; -\; c)\; OPT\; \{\backslash \; displaystyle\; (1-\; c)\; \backslash \; mathrm\; \{OPT\}\}$	$(1\; -\; c)\; OPT\; +\; c\; WORST\; \{\backslash \; displaystyle\; (1-c)\; \backslash \; mathrm\; \{OPT\}\; +\; c\; \backslash \; mathrm\; \{WORST\}\}$	$OPT\; -\; c\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{OPT\}\; -c\}$
min: $f\; (x)\; \le \; \{\backslash \; displaystyle\; f\; (x)\; \backslash \; leq\}$	$r\; OPT\; \{\backslash \; displaystyle\; r\; \backslash \; mathrm\; \{OPT\}\}$	$\rho \; OPT\; \{\backslash \; displaystyle\; \backslash \; rho\; \backslash \; mathrm\; \{OPT\}\}$	$(1\; +\; c)\; OPT\; \{\backslash \; displaystyle\; (1\; +\; c)\; \backslash \; mathrm\; \{OPT\}\}$	$(1\; -\; c)\; -\; 1\; OPT\; \{\backslash \; displaystyle\; (\; 1-c)\; ^\; \{-\; 1\}\; \backslash \; mathrm\; \{OPT\}\}$	$(1\; -\; c)\; -\; 1\; OPT\; +\; c\; НАИЛУЧШИЙ\; \{\backslash \; displaystyle\; (1-c)\; ^\; \{-\; 1\}\; \backslash \; mathrm\; \{OPT\}\; +\; c\; \backslash \; mathrm\; \{WORST\}\}$	$OPT\; +\; c\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{OPT\}\; +\; c\}$

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

-член может появиться, когда алгоритм аппроксимации вводит мультипликативную ошибку и постоянную ошибку, в то время как минимальный оптимум экземпляры размера n стремятся к бесконечности, как и n. В этом случае коэффициент аппроксимации равен c ∓ k / OPT = c ∓ o (1) для некоторых констант c и k. Для произвольного ϵ>0 можно выбрать достаточно большое N, чтобы член k / OPT < ϵ for every n ≥ N. For every fixed ϵ, instances of size n < N can be solved by brute force, thereby showing an approximation ratio — existence of approximation algorithms with a guarantee — of c ∓ ϵ for every ϵ>0.

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

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

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