В информатике и исследование операций , алгоритмы аппроксимации являются эффективными алгоритмами , которые находят приближенный решения задач оптимизации (в частности , NP-трудных задачах) с доказательными гарантиями на расстоянии возвращенного решения оптимального. [1] Аппроксимационные алгоритмы естественным образом возникают в области теоретической информатики как следствие широко распространенной гипотезы P ≠ NP . Согласно этой гипотезе, широкий класс задач оптимизации не может быть решен точно за полиномиальное время.. Поэтому область аппроксимационных алгоритмов пытается понять, насколько точно можно аппроксимировать оптимальные решения таких задач за полиномиальное время. В подавляющем большинстве случаев гарантия таких алгоритмов является мультипликативной, выраженной как коэффициент аппроксимации или коэффициент аппроксимации, т.е. оптимальное решение всегда гарантированно находится в пределах (заранее определенного) мультипликативного коэффициента возвращенного решения. Однако существует также множество алгоритмов аппроксимации, которые обеспечивают дополнительную гарантию качества возвращаемого решения. Ярким примером алгоритма приближения, который обеспечивает оба, является классический алгоритм приближения Ленстры , Шмойса и Тардоса [2] для планирования на несвязанных параллельных машинах .
Разработка и анализ алгоритмов аппроксимации критически включает математическое доказательство, удостоверяющее качество возвращаемых решений в худшем случае. [1] Это отличает их от эвристических алгоритмов , таких как отжиг или генетических алгоритмов , которые находят достаточно хорошие решения для некоторых входных данных, но не дают четкого указания с самого начала, когда они могут быть успешными или неудачными.
Теоретическая информатика проявляет большой интерес к лучшему пониманию пределов, до которых мы можем приблизиться к некоторым известным задачам оптимизации. Например, один из давних открытых вопросов в информатике - определить, существует ли алгоритм, который превосходит алгоритм аппроксимации 1,5 Кристофидеса для метрической задачи коммивояжера . Желание понять сложные проблемы оптимизации с точки зрения аппроксимируемости мотивировано открытием удивительных математических связей и широко применимых методов для разработки алгоритмов для сложных задач оптимизации. Одним из хорошо известных примеров первого является алгоритм Гоэманса – Вильямсона для максимального разреза , который решает теоретико-графическую задачу с использованием геометрии большой размерности. [3]
Вступление
Простой пример алгоритма аппроксимации - это алгоритм для задачи о минимальном покрытии вершин , где цель состоит в том, чтобы выбрать наименьшее множество вершин, такое, чтобы каждое ребро во входном графе содержало по крайней мере одну выбранную вершину. Один из способов найти покрытие вершины - повторить следующий процесс: найти непокрытое ребро, добавить оба его конца к покрытию и удалить все ребра, инцидентные любой вершине из графа. Поскольку любое вершинное покрытие входного графа должно использовать отдельную вершину для покрытия каждого ребра, которое было рассмотрено в процессе (поскольку оно формирует соответствие ), полученное вершинное покрытие, следовательно, не более чем в два раза больше оптимального. Другими словами, это алгоритм аппроксимации с постоянным коэффициентом с коэффициентом аппроксимации, равным 2. Согласно недавней гипотезе об уникальных играх , этот коэффициент является даже наилучшим из возможных. [4]
NP-сложные задачи сильно различаются по аппроксимируемости; некоторые, такие как задача о рюкзаке , могут быть аппроксимированы с помощью мультипликативного множителя, для любых фиксированных , и поэтому производят решения, сколь угодно близкие к оптимальным (такое семейство алгоритмов аппроксимации называется схемой аппроксимации с полиномиальным временем или PTAS). Другие невозможно аппроксимировать в рамках какого-либо постоянного или даже полиномиального множителя, если только P = NP , как в случае задачи о максимальной клике . Таким образом, важным преимуществом изучения алгоритмов аппроксимации является детальная классификация сложности различных NP-сложных задач, выходящая за рамки той, которая предоставляется теорией NP-полноты . Другими словами, хотя 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 по Санджив Арору (и независимо Joseph Mitchell ) , который имел запретительное время работы для приближение. [9] Тем не менее, в течение года эти идеи были включены в почти линейное время. алгоритм для любой константы . [10]
Гарантии производительности
Для некоторых алгоритмов аппроксимации можно доказать определенные свойства приближения к оптимальному результату. Например, алгоритм A ρ- аппроксимации определяется как алгоритм, для которого было доказано, что значение / стоимость, f ( x ), приближенного решения A ( x ) для экземпляра x не будет больше (или меньше, в зависимости от ситуации), чем коэффициент ρ, умноженный на значение OPT оптимального решения.
Коэффициент ρ называется относительной гарантией производительности . Алгоритм аппроксимации имеет абсолютную гарантию производительности или ограниченную ошибку c , если для каждого экземпляра x было доказано, что
Аналогичным образом , гарантия исполнения , Р ( х, у ), из раствора у к экземпляру х определяется как
где f ( y ) - стоимость / стоимость решения y для экземпляра x . Ясно, что гарантия производительности больше или равна 1 и равна 1 тогда и только тогда, когда y является оптимальным решением. Если алгоритм A гарантирует возврат решений с гарантией производительности при большем г ( п ), то называется быть г ( п ) -аппроксимация алгоритм и имеет коэффициент аппроксимации по г ( п ). Кроме того, проблема с г ( п ) -аппроксимация алгоритм назовет г ( п ) - аппроксимируемо или иметь коэффициент аппроксимации г ( п ). [11] [12]
Для задач минимизации две разные гарантии обеспечивают один и тот же результат, а для задач максимизации относительная гарантия производительности ρ эквивалентна гарантии производительности . В литературе используются оба определения, но ясно, какое определение используется, поскольку для задач максимизации, как ρ ≤ 1, а r ≥ 1.
Гарантия абсолютной производительности некоторого алгоритма аппроксимации A , где x относится к экземпляру проблемы, а гдеявляется гарантией производительности A на x (то есть ρ для экземпляра проблемы x ):
То есть сказать, что - это наибольшая граница отношения аппроксимации r , которую можно увидеть по всем возможным случаям проблемы. Аналогичным образом, асимптотический коэффициент производительности является:
То есть это то же самое, что и абсолютный коэффициент производительности , с нижней границей n для размера проблемных экземпляров. Эти два типа соотношений используются, потому что существуют алгоритмы, в которых разница между ними значительна.
r -прибл. [11] [12] | ρ -прибл. | отн. ошибка [12] | отн. ошибка [11] | норма. отн. ошибка [11] [12] | абс. ошибка [11] [12] | |
---|---|---|---|---|---|---|
Максимум: | ||||||
мин: |
Условия использования 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
Смотрите также
- Анализ доминирования рассматривает гарантии с точки зрения ранга вычисленного решения.
- PTAS - тип алгоритма аппроксимации, который принимает коэффициент аппроксимации в качестве параметра
- APX - это класс задач с некоторым алгоритмом аппроксимации с постоянным коэффициентом.
- Приведение с сохранением приближения
- Точный алгоритм
Цитаты
- ^ 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, Michel 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 .
- ^ Арора, С. (октябрь 1996 г.). Схемы полиномиальной аппроксимации по времени для евклидовой ЗК и других геометрических задач . Материалы 37-й конференции по основам информатики . С. 2–11. CiteSeerX 10.1.1.32.3376 . DOI : 10.1109 / SFCS.1996.548458 . ISBN 978-0-8186-7594-2.
- ^ Арора, С. (октябрь 1997 г.). Схемы аппроксимации почти линейного времени для евклидовой ЗК и других геометрических задач . Труды 38-го ежегодного симпозиума по основам информатики . С. 554–563. DOI : 10.1109 / SFCS.1997.646145 . ISBN 978-0-8186-8197-4.
- ^ а б в г д Г. Аузиелло; П. Крещенци; Г. Гамбози; В. Канн; А. Маркетти-Спаккамела; М. Протаси (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 .