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

Класс алгоритмов, находящих приближенные решения задач оптимизации.

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

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

Существует широкий интерес к теоретической информатике , чтобы лучше понять пределы, до которых мы можем приблизиться к некоторым известным задачам оптимизации. Например, одним из давних открытых вопросов в информатике является определение того, существует ли алгоритм, который превосходит 2-приближение для задачи Штайнера Фореста, предложенное Агравалом и др. ^[3] Желание понять сложные задачи оптимизации с точки зрения аппроксимации мотивировано открытием удивительных математических связей и широко применимых методов разработки алгоритмов для решения сложных задач оптимизации. Одним из хорошо известных примеров первого является алгоритм Гоеманса-Вильямсона для максимального сечения , который решает задачу теории графов с использованием многомерной геометрии. ^[4]

Введение

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

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

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

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

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

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

Хотя алгоритмы аппроксимации всегда обеспечивают априорную гарантию наихудшего случая (будь то аддитивную или мультипликативную), в некоторых случаях они также предоставляют апостериорную гарантию, которая часто намного лучше. Это часто относится к алгоритмам, которые работают путем решения выпуклой релаксации задачи оптимизации на заданных входных данных. Например, существует другой алгоритм аппроксимации минимального вершинного покрытия, который решает задачу релаксации линейного программирования и находит вершинное покрытие, которое не более чем в два раза превышает значение релаксации. Поскольку значение релаксации никогда не превышает размера оптимального вершинного покрытия, это дает еще один алгоритм 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] ${\displaystyle n^{O(1/\epsilon )}}$ ${\displaystyle 1+\epsilon }$ ${\displaystyle O(n\log n)}$ ${\displaystyle \epsilon >0}$

Гарантии производительности

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

${\displaystyle {\begin{cases}\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).}$

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

${\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 ), то A называется алгоритмом r ( n )-аппроксимации и имеет коэффициент аппроксимации r ( n ). Аналогично, задача с алгоритмом r ( n )-аппроксимации называется r ( n ) -аппроксимируемой или имеет коэффициент аппроксимации r ( n ). ^{[12] [13]}

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

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

${\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,\forall x,|x|\geq n\}.}$

То есть это то же самое, что и абсолютный коэффициент производительности , с нижней границей 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.

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

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

Цитаты

1. Бернард., Шмойс, Дэвид (2011). Разработка аппроксимационных алгоритмов. Издательство Кембриджского университета. ISBN 9780521195270. ОСЛК  671709856.{{cite book}}: CS1 maint: multiple names: authors list (link)
2. Ленстра, Ян Карел; Шмойс, Дэвид Б.; Тардос, Ева (1 января 1990 г.). «Аппроксимационные алгоритмы планирования несвязанных параллельных машин». Математическое программирование . 46 (1–3): 259–271. CiteSeerX 10.1.1.115.708 . дои : 10.1007/BF01585745. ISSN  0025-5610. S2CID  206799898. 
3. Агравал, Аджит; Кляйн, Филип; Рави, Р. (1991). «Когда деревья сталкиваются». Материалы двадцать третьего ежегодного симпозиума ACM по теории вычислений - STOC '91 . Новый Орлеан, Луизиана, США: ACM Press. стр. 134–144. дои : 10.1145/103418.103437. ISBN 978-0-89791-397-3. S2CID  1245448.
4. Гоеманс, Мишель X.; Уильямсон, Дэвид П. (ноябрь 1995 г.). «Улучшенные алгоритмы аппроксимации для задач максимального разреза и выполнимости с использованием полуопределенного программирования». Дж. АКМ . 42 (6): 1115–1145. CiteSeerX 10.1.1.34.8500 . дои : 10.1145/227683.227684. ISSN  0004-5411. S2CID  15794408. 
5. Хот, Субхаш; Регев, Одед (01 мая 2008 г.). «Покрытие вершин может быть трудно аппроксимировать с точностью до 2−ε». Журнал компьютерных и системных наук . Вычислительная сложность 2003. 74 (3): 335–349. дои : 10.1016/j.jcss.2007.06.019 .
6. Карпински, Марек; Лампис, Майкл; Шмид, Ричард (01 декабря 2015 г.). «Новые границы неприближаемости для TSP». Журнал компьютерных и системных наук . 81 (8): 1665–1677. arXiv : 1303.6437 . дои : 10.1016/j.jcss.2015.06.003.
7. Файги, Уриэль; Гольдвассер, Шафи; Ловас, Ласло; Сафра, Шмуэль; Сегеди, Марио (март 1996 г.). «Интерактивные доказательства и жесткость аппроксимирующих клик». Дж. АКМ . 43 (2): 268–292. дои : 10.1145/226643.226652 . ISSN  0004-5411.
8. Арора, Санджив; Сафра, Шмуэль (январь 1998 г.). «Вероятностная проверка доказательств: новая характеристика NP». Дж. АКМ . 45 (1): 70–122. дои : 10.1145/273865.273901 . ISSN  0004-5411. S2CID  751563.
9. Джонсон, Дэвид С. (1 декабря 1974 г.). «Алгоритмы аппроксимации комбинаторных задач». Журнал компьютерных и системных наук . 9 (3): 256–278. дои : 10.1016/S0022-0000(74)80044-9 .
10. Арора, С. (октябрь 1996 г.). «Схемы аппроксимации полиномиального времени для евклидовой коммерческой задачи и других геометрических задач». Материалы 37-й конференции по основам информатики . стр. 2–11. CiteSeerX 10.1.1.32.3376 . дои : 10.1109/SFCS.1996.548458. ISBN  978-0-8186-7594-2. S2CID  1499391.
11. Арора, С. (октябрь 1997 г.). «Схемы аппроксимации почти линейного времени для евклидовой коммерческой задачи и других геометрических задач». Материалы 38-го ежегодного симпозиума по основам информатики . стр. 554–563. дои : 10.1109/SFCS.1997.646145. ISBN 978-0-8186-8197-4. S2CID  10656723.
12. Г. Аузиелло; П. Крещенци; Г. Гамбози; В. Канн; А. Маркетти-Спаккамела; М. Протаси (1999). Сложность и аппроксимация: задачи комбинаторной оптимизации и их свойства аппроксимации .
13. Вигго Канн (1992). Об аппроксимируемости NP-полных задач оптимизации (PDF) .
14. Йохан Хостад (1999). «Некоторые оптимальные результаты неаппроксимируемости». Журнал АКМ . 48 (4): 798–859. CiteSeerX 10.1.1.638.2808 . дои : 10.1145/502090.502098. S2CID  5120748. 

Рекомендации

• Вазирани, Виджай В. (2003). Алгоритмы аппроксимации . Берлин: Шпрингер. 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.