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

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

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

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

Введение

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

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

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

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

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

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

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

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

Учитывая задачу оптимизации:

$\Pi :I\times S$

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

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

и множество допустимых решений:

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

найти лучшее решение $s^{*}$ для задачи максимизации или минимизации:

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

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

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

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

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

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

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

{\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 что

(\mathrm {OPT} -c)\leq f(x)\leq (\mathrm {OPT} +c).

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

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]

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

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

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

То есть $\mathrm {P} _{A}$ — это наибольшая граница коэффициента аппроксимации r , которую можно увидеть во всех возможных случаях задачи. Аналогично, асимптотический коэффициент производительности $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 размера экземпляров проблемы. Эти два типа отношений используются потому, что существуют алгоритмы, в которых разница между ними значительна.

Гарантии производительности
	г -приблизительно ^[12]^[13]	ρ -ок .	отн. ошибка ^[13]	отн. ошибка ^[12]	норма. отн. ошибка ^[12]^[13]	абс. ошибка ^[12]^[13]
Макс: $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$

Условия Эпсилон

В литературе коэффициент аппроксимации для задачи максимизации (минимизации) 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 - это класс задач с некоторым алгоритмом аппроксимации с постоянным коэффициентом.
Приведение с сохранением аппроксимации
Точный алгоритм

Цитаты

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

Ссылки

Vazirani, Vijay V. (2003). Approximation Algorithms . Berlin: 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 г.), Разработка алгоритмов аппроксимации , Cambridge University Press , ISBN 978-0521195270

Внешние ссылки

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

[Bernard._2011-1] Jump up to: ^а ^б Бернард., Шмойс, Дэвид (2011). Разработка аппроксимирующих алгоритмов . Издательство Кембриджского университета. ISBN 9780521195270 . OCLC 671709856 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

[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] Хот, Субхаш; Регев, Одед (1 мая 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 .

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

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

[hastad99someoptimal-14] Йохан Хостад (1999). «Некоторые оптимальные результаты неаппроксимируемости» . Журнал АКМ . 48 (4): 798–859. CiteSeerX 10.1.1.638.2808 . дои : 10.1145/502090.502098 . S2CID 5120748 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]