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

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

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

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

В теоретической информатике широко распространен интерес к лучшему пониманию пределов, до которых мы можем аппроксимировать некоторые известные задачи оптимизации. Например, одним из давних открытых вопросов в информатике является определение того, существует ли алгоритм, который превосходит 2-аппроксимацию для задачи Steiner Forest Агравала и др. ^[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-х годов, такие результаты были получены ad hoc средствами, и в то время не было никакого систематического понимания. Только после результата 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}$

Структура алгоритмов аппроксимации

Дана задача оптимизации:

${\displaystyle \Pi :I\times S}$

где — задача аппроксимации, набор входных данных и набор решений, мы можем определить функцию стоимости: ${\displaystyle \Pi }$ ${\displaystyle I}$ ${\displaystyle S}$

${\displaystyle c:S\rightarrow \mathbb {R} ^{+}}$

и набор возможных решений:

${\displaystyle \forall i\in I,S(i)={s\in S:i\Pi _{s}}}$

поиск наилучшего решения для задачи максимизации или минимизации: ${\displaystyle s^{*}}$

${\displaystyle s^{*}\in S(i)}$, ${\displaystyle c(s^{*})=min/max\ c(S(i))}$

При наличии допустимого решения , при , мы хотели бы получить гарантию качества решения, то есть производительности, которая должна быть гарантирована (коэффициент аппроксимации). ${\displaystyle s\in S(i)}$ ${\displaystyle s\neq s^{*}}$

В частности, имея , алгоритм имеет коэффициент аппроксимации (или отношение аппроксимации ), равный , если , то мы имеем: ${\displaystyle A_{\Pi }(i)\in S_{i}}$ ${\displaystyle \rho (n)}$ ${\displaystyle \forall i\in I\ s.t.|i|=n}$

• для задачи минимизации : , что в свою очередь означает, что решение, принятое алгоритмом, деленное на оптимальное решение, достигает соотношения ; ${\displaystyle {\frac {c(A_{\Pi }(i))}{c(s^{*}(i))}}\leq \rho (n)}$ ${\displaystyle \rho (n)}$
• для задачи максимизации : , что в свою очередь означает, что оптимальное решение, деленное на решение, принятое алгоритмом, достигает соотношения ; ${\displaystyle {\frac {c(s^{*}(i))}{c(A_{\Pi }(i))}}\leq \rho (n)}$ ${\displaystyle \rho (n)}$

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

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

Для некоторых алгоритмов приближения можно доказать определенные свойства приближения оптимального результата. Например, алгоритм ρ -приближения 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 - ϵ (min: 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. Bernard., Shmoys, David (2011). Разработка алгоритмов аппроксимации. Cambridge University Press. ISBN 9780521195270. OCLC  671709856.{{cite book}}: CS1 maint: multiple names: authors list (link)
2. Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (1990-01-01). «Аппроксимационные алгоритмы для планирования не связанных параллельных машин». Математическое программирование . 46 (1–3): 259–271. CiteSeerX 10.1.1.115.708 . doi :10.1007/BF01585745. ISSN  0025-5610. S2CID  206799898. 
3. Агравал, Аджит; Кляйн, Филип; Рави, Р. (1991). «Когда деревья сталкиваются». Труды двадцать третьего ежегодного симпозиума ACM по теории вычислений — STOC '91 . Новый Орлеан, Луизиана, США: ACM Press. стр. 134–144. doi :10.1145/103418.103437. ISBN 978-0-89791-397-3. S2CID  1245448.
4. Goemans, Michel X.; Williamson, David P. (ноябрь 1995 г.). «Улучшенные алгоритмы аппроксимации для задач максимального разреза и выполнимости с использованием полуопределенного программирования». J. ACM . 42 (6): 1115–1145. CiteSeerX 10.1.1.34.8500 . doi :10.1145/227683.227684. ISSN  0004-5411. S2CID  15794408. 
5. Хот, Субхаш; Регев, Одед (2008-05-01). "Покрытие вершин может быть трудно аппроксимировать с точностью до 2−ε". Журнал компьютерных и системных наук . Вычислительная сложность 2003. 74 (3): 335–349. doi : 10.1016/j.jcss.2007.06.019 .
6. Карпински, Марек; Лампис, Михаэль; Шмид, Ричард (2015-12-01). «Новые границы неаппроксимируемости для TSP». Журнал компьютерных и системных наук . 81 (8): 1665–1677. arXiv : 1303.6437 . doi : 10.1016/j.jcss.2015.06.003.
7. Файги, Уриэль; Гольдвассер, Шафи; Ловас, Ласло; Сафра, Шмуэль; Сегеди, Марио (март 1996 г.). «Интерактивные доказательства и жесткость аппроксимирующих клик». Дж. АКМ . 43 (2): 268–292. дои : 10.1145/226643.226652 . ISSN  0004-5411.
8. Арора, Санджив; Сафра, Шмуэль (январь 1998 г.). «Вероятностная проверка доказательств: новая характеристика NP». J. ACM . 45 (1): 70–122. doi : 10.1145/273865.273901 . ISSN  0004-5411. S2CID  751563.
9. Джонсон, Дэвид С. (1974-12-01). «Аппроксимационные алгоритмы для комбинаторных задач». Журнал компьютерных и системных наук . 9 (3): 256–278. doi : 10.1016/S0022-0000(74)80044-9 .
10. Arora, S. (октябрь 1996 г.). "Схемы полиномиального времени аппроксимации для евклидовых задач коммивояжера и других геометрических задач". Труды 37-й конференции по основам компьютерных наук . стр. 2–11. CiteSeerX 10.1.1.32.3376 . doi :10.1109/SFCS.1996.548458. ISBN  978-0-8186-7594-2. S2CID  1499391.
11. Арора, С. (октябрь 1997 г.). «Почти линейные схемы аппроксимации времени для евклидовых задач коммивояжера и других геометрических задач». Труды 38-го ежегодного симпозиума по основам компьютерной науки . стр. 554–563. doi :10.1109/SFCS.1997.646145. ISBN 978-0-8186-8197-4. S2CID  10656723.
12. G. Ausiello; P. Crescenzi; G. Gambosi; V. Kann; A. Marchetti-Spaccamela; M. Protasi (1999). Сложность и аппроксимация: задачи комбинаторной оптимизации и их свойства аппроксимируемости .
13. Вигго Канн (1992). Об аппроксимируемости NP-полных задач оптимизации (PDF) .
14. Йохан Хастад (1999). «Некоторые оптимальные результаты неаппроксимируемости». Журнал ACM . 48 (4): 798–859. CiteSeerX 10.1.1.638.2808 . doi :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.