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

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

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

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

Введение [ править ]

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

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

Методы разработки алгоритмов [ править ]

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

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

Апостериорные гарантии [ править ]

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

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

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

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

Практичность [ править ]

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

В других случаях, даже если первоначальные результаты представляют чисто теоретический интерес, со временем, с улучшенным пониманием, алгоритмы могут быть усовершенствованы, чтобы стать более практичными. Одним из таких примеров является начальный PTAS для евклидовой TSP, разработанный Сандживом Аророй (и независимо Джозефом Митчеллом ), у которого было недопустимое время работы для приближения. ^[9] Тем не менее, в течение года эти идеи были включены в алгоритм почти линейного времени для любой постоянной . ^[10] ${\ 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 гарантирует возврат решений с гарантией производительности при большем г ( п ), то называется быть г ( п ) -аппроксимация алгоритм и имеет коэффициент аппроксимации по г ( п ). Точно так же проблема с r ( n) -аппроксимация алгоритм назовем г ( п ) - аппроксимируемы или иметь коэффициент аппроксимации г ( п ). ^[11]^[12]

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

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

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

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

R_{A}^{\infty }=\inf\{r\geq 1\mid \exists n\in \mathbb {Z} ^{+},R_{A}(x)\leq r,\forall x,|x|\geq n\}.

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

Гарантии производительности
	r -прибл. ^[11]^[12]	ρ -прибл.	отн. ошибка ^[12]	отн. ошибка ^[11]	норма. отн. ошибка ^[11]^[12]	абс. ошибка ^[11]^[12]
Максимум: $f(x)\geq$	$r^{-1}\mathrm {OPT}$	$\rho \mathrm {OPT}$	$(1-c)\mathrm {OPT}$	$(1-c)\mathrm {OPT}$	$(1-c)\mathrm {OPT} +c\mathrm {WORST}$	$\mathrm {OPT} -c$
мин: $f(x)\leq$	$r\mathrm {OPT}$	$\rho \mathrm {OPT}$	$(1+c)\mathrm {OPT}$	$(1-c)^{-1}\mathrm {OPT}$	$(1-c)^{-1}\mathrm {OPT} +c\mathrm {WORST}$	$\mathrm {OPT} +c$

Условия Epsilon [ править ]

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

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

См. Также [ править ]

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

Цитаты [ править ]

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

^ a b Бернард., Шмойс, Дэвид (2011). Дизайн аппроксимационных алгоритмов . Издательство Кембриджского университета. ISBN 9780521195270. OCLC 671709856 .
^ Ленстра, Ян Карел; Шмойс, Давид Б .; Тардос, Ива (01.01.1990). «Алгоритмы аппроксимации для планирования несвязанных параллельных машин». Математическое программирование . 46 (1–3): 259–271. CiteSeerX 10.1.1.115.708 . DOI : 10.1007 / BF01585745 . ISSN 0025-5610 .
^ Goemans, Мишель X .; Уильямсон, Дэвид П. (ноябрь 1995 г.). «Улучшенные алгоритмы аппроксимации для задач максимального разреза и выполнимости с использованием полуопределенного программирования». J. ACM . 42 (6): 1115–1145. CiteSeerX 10.1.1.34.8500 . DOI : 10.1145 / 227683.227684 . ISSN 0004-5411 .
^ Хот, Субхаш; Регев, Одед (1 мая 2008 г.). «Покрытие вершины может быть трудно аппроксимировать с точностью до 2-ε». Журнал компьютерных и системных наук . Вычислительная сложность 2003. 74 (3): 335–349. DOI : 10.1016 / j.jcss.2007.06.019 .
^ Карпинский, Марек; Лэмпис, Майкл; Шмид, Ричард (01.12.2015). «Новые границы неапроксимируемости ЗК». Журнал компьютерных и системных наук . 81 (8): 1665–1677. arXiv : 1303,6437 . DOI : 10.1016 / j.jcss.2015.06.003 .
^ Файги, Уриэль; Гольдвассер, Шафи; Ловас, Ласло; Сафра, Шмуэль; Сегеди, Марио (март 1996). «Интерактивные доказательства и твердость аппроксимирующих клик» . J. ACM . 43 (2): 268–292. DOI : 10.1145 / 226643.226652 . ISSN 0004-5411 .
^ Арора, Санджив; Сафра, Шмуэль (январь 1998 г.). «Вероятностная проверка доказательств: новая характеристика NP». J. ACM . 45 (1): 70–122. DOI : 10.1145 / 273865.273901 . ISSN 0004-5411 .
^ Джонсон, Дэвид С. (1974-12-01). «Аппроксимационные алгоритмы комбинаторных задач». Журнал компьютерных и системных наук . 9 (3): 256–278. DOI : 10.1016 / S0022-0000 (74) 80044-9 .
Перейти ↑ Arora, S. (октябрь 1996 г.). Схемы полиномиальной аппроксимации по времени для евклидовой ЗК и других геометрических задач . Материалы 37-й конференции по основам информатики . С. 2–11. CiteSeerX 10.1.1.32.3376 . DOI : 10.1109 / SFCS.1996.548458 . ISBN 978-0-8186-7594-2.
Перейти ↑ Arora, S. (октябрь 1997 г.). Схемы аппроксимации почти линейного времени для евклидовой ЗК и других геометрических задач . Труды 38-го ежегодного симпозиума по основам информатики . С. 554–563. DOI : 10.1109 / SFCS.1997.646145 . ISBN 978-0-8186-8197-4.
^ a b c d e Г. Осиелло; П. Крещенци; Г. Гамбози; В. Канн; А. Маркетти-Спаккамела; М. Протаси (1999). Сложность и аппроксимация: задачи комбинаторной оптимизации и их свойства аппроксимируемости .
^ а б в г д Вигго Канн (1992). Об аппроксимируемости NP-полных задач оптимизации (PDF) .
^ Джоен Хастад (1999). «Некоторые результаты оптимальной несовместимости» . Журнал ACM . 48 (4): 798–859. CiteSeerX 10.1.1.638.2808 . DOI : 10.1145 / 502090.502098 .

Ссылки [ править ]

Вазирани, Виджай В. (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 .

[Bernard._2011-1] Бернард., Шмойс, Дэвид (2011). Дизайн аппроксимационных алгоритмов . Издательство Кембриджского университета. ISBN 9780521195270. OCLC 671709856 .

[2] Ленстра, Ян Карел; Шмойс, Давид Б .; Тардос, Ива (01.01.1990). «Алгоритмы аппроксимации для планирования несвязанных параллельных машин». Математическое программирование . 46 (1–3): 259–271. CiteSeerX 10.1.1.115.708 . DOI : 10.1007 / BF01585745 . ISSN 0025-5610 .

[3] Goemans, Мишель X .; Уильямсон, Дэвид П. (ноябрь 1995 г.). «Улучшенные алгоритмы аппроксимации для задач максимального разреза и выполнимости с использованием полуопределенного программирования». J. ACM . 42 (6): 1115–1145. CiteSeerX 10.1.1.34.8500 . DOI : 10.1145 / 227683.227684 . ISSN 0004-5411 .

[4] Хот, Субхаш; Регев, Одед (1 мая 2008 г.). «Покрытие вершины может быть трудно аппроксимировать с точностью до 2-ε». Журнал компьютерных и системных наук . Вычислительная сложность 2003. 74 (3): 335–349. DOI : 10.1016 / j.jcss.2007.06.019 .

[5] Карпинский, Марек; Лэмпис, Майкл; Шмид, Ричард (01.12.2015). «Новые границы неапроксимируемости ЗК». Журнал компьютерных и системных наук . 81 (8): 1665–1677. arXiv : 1303,6437 . DOI : 10.1016 / j.jcss.2015.06.003 .

[6] Файги, Уриэль; Гольдвассер, Шафи; Ловас, Ласло; Сафра, Шмуэль; Сегеди, Марио (март 1996). «Интерактивные доказательства и твердость аппроксимирующих клик» . J. ACM . 43 (2): 268–292. DOI : 10.1145 / 226643.226652 . ISSN 0004-5411 .

[7] Арора, Санджив; Сафра, Шмуэль (январь 1998 г.). «Вероятностная проверка доказательств: новая характеристика NP». J. ACM . 45 (1): 70–122. DOI : 10.1145 / 273865.273901 . ISSN 0004-5411 .

[8] Джонсон, Дэвид С. (1974-12-01). «Аппроксимационные алгоритмы комбинаторных задач». Журнал компьютерных и системных наук . 9 (3): 256–278. DOI : 10.1016 / S0022-0000 (74) 80044-9 .

[9] Перейти ↑ Arora, S. (октябрь 1996 г.). Схемы полиномиальной аппроксимации по времени для евклидовой ЗК и других геометрических задач . Материалы 37-й конференции по основам информатики . С. 2–11. CiteSeerX 10.1.1.32.3376 . DOI : 10.1109 / SFCS.1996.548458 . ISBN 978-0-8186-7594-2.

[10] Перейти ↑ Arora, S. (октябрь 1997 г.). Схемы аппроксимации почти линейного времени для евклидовой ЗК и других геометрических задач . Труды 38-го ежегодного симпозиума по основам информатики . С. 554–563. DOI : 10.1109 / SFCS.1997.646145 . ISBN 978-0-8186-8197-4.

[ausiello99complexity-11] Г. Осиелло; П. Крещенци; Г. Гамбози; В. Канн; А. Маркетти-Спаккамела; М. Протаси (1999). Сложность и аппроксимация: задачи комбинаторной оптимизации и их свойства аппроксимируемости .

[kann92onthe-12] а б в г д Вигго Канн (1992). Об аппроксимируемости NP-полных задач оптимизации (PDF) .

[hastad99someoptimal-13] Джоен Хастад (1999). «Некоторые результаты оптимальной несовместимости» . Журнал ACM . 48 (4): 798–859. CiteSeerX 10.1.1.638.2808 . DOI : 10.1145 / 502090.502098 .

[1]