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

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

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

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

Вступление

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

NP-сложные задачи сильно различаются по аппроксимируемости; некоторые, такие как проблема с рюкзаком, можно аппроксимировать с точностью до множителя ${ displaystyle 1+ epsilon}$, для любых фиксированных ${ displaystyle 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.^[5] В сочетании со знанием существования приближенного алгоритма Христофидеса 1.5 это говорит нам, что порог аппроксимируемости для метрического коммивояжера (если он есть) находится где-то между 123/122 и 1,5.

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

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

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

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

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

Для некоторых алгоритмов аппроксимации можно доказать определенные свойства приближения к оптимальному результату. Например, ρ-приближенный алгоритм А определяется как алгоритм, для которого было доказано, что значение / стоимость, ж(Икс) приближенного решения А(Икс) к экземпляру Икс не будет больше (или меньше, в зависимости от ситуации) фактора ρ умноженное на значение 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, если это доказано для каждого случая Икс который

${ 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),}$

куда ж(у) - стоимость / стоимость решения у для примера Икс. Ясно, что гарантия производительности больше или равна 1 и равна 1 тогда и только тогда, когда у оптимальное решение. Если алгоритм А гарантирует возврат решений с гарантией производительности не более р(п), тогда А считается р(п) -аппроксимации и имеет коэффициент аппроксимации из р(п). Точно так же проблема с р(п) -приближенный алгоритм называется r(п)-приближенный или иметь коэффициент аппроксимации р(п).^[11][12]

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

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

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

То есть сказать, что ${ 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 }.}$

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

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

	р-приблизительно[11][12]	ρ-приблизительно	отн. ошибка[12]	отн. ошибка[11]	норма. отн. ошибка[11][12]	абс. ошибка[11][12]
Максимум: ${ Displaystyle е (х) geq}$	${ Displaystyle г ^ {- 1} mathrm {ОПТ}}$	${ 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-c) ^ {- 1} mathrm {OPT}}$	${ displaystyle (1-c) ^ {- 1} mathrm {OPT} + c mathrm {НАИЛУЧШИЙ}}$	${ displaystyle mathrm {OPT} + c}$

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

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

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

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

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

Цитаты

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

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

внешняя ссылка

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