Приведение с сохранением аппроксимации

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

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

Определение

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

Пусть $A$ и $B$ — задачи оптимизации.

Пусть $x$ — экземпляр задачи $A$ с оптимальным решением ${\text{OPT}}(x)$ . Позволять $c_{A}(x,y)$ стоимость решения $y$ экземпляра $x$ проблемы $A.$ обозначаем Это также метрика, используемая для определения того, какое решение считается оптимальным.

Приведение , сохраняющее аппроксимацию, представляет собой пару функций $(f,g)$ (который часто должен быть вычислим за полиномиальное время), такой что:

$f$ отображает экземпляр $x$ экземпляра $A$ в экземпляр $x'$ Б. $$
$g$ отображает решение $y'$ B $$ к решению $y$ A $$ .
$g$ решения сохраняет некоторую гарантию производительности или , коэффициент аппроксимации определяемый как $R_{A}(x,y)=\max \left({\frac {c_{A}(x,{\text{OPT}}(x))}{c_{A}(x,y)}},{\frac {c_{A}(x,y)}{c_{A}(x,{\text{OPT}}(x))}}\right)$ .

Типы

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

Не все типы сохраняющих аппроксимацию сокращений можно использовать для демонстрации принадлежности ко всем классам сложности аппроксимации, наиболее известными из которых являются PTAS и APX . Приведенное ниже сокращение сохраняет принадлежность к классу сложности C, если для данной проблемы A, которая сводится к проблеме B через схему редукции, и B находится в C, то A также находится в C. Некоторые сокращения, показанные ниже, сохраняют только членство в APX или PTAS, но не в другом. Из-за этого необходимо делать тщательный выбор при выборе сохраняющих аппроксимацию сокращений, особенно с целью доказательства полноты задачи в пределах класса сложности.

Крещенци предполагает, что тремя наиболее идеальными стилями снижения, как с точки зрения простоты использования, так и с точки зрения эффективности, являются снижение PTAS, снижение AP и L-редукция. ^[1] Следующие ниже описания редукций взяты из обзора Кресченци редукций, сохраняющих аппроксимацию.

Строгое сокращение

Строгая редукция - это самый простой тип редукции, сохраняющей аппроксимацию. При строгом сокращении коэффициент аппроксимации решения y' к экземпляру x' проблемы B должен быть не более, чем коэффициент аппроксимации соответствующего решения y к экземпляру x проблемы A. Другими словами:

R_{A}(x,y)\leq R_{B}(x',y')

для

x'=f(x),y=g(y')

.

Строгая редукция является наиболее простой: если строгая редукция от проблемы A к проблеме B существует, то проблема A всегда может быть аппроксимирована по крайней мере с таким же хорошим соотношением, как и проблема B. Строгая редукция сохраняет членство как в PTAS, так и в APX.

Существует аналогичное понятие S-редукции, для которого $c_{A}(x,y)=c_{B}(x',y')$ , и оптимумы двух соответствующих экземпляров также должны иметь одинаковую стоимость. S-редукция — это особый случай строгой редукции, и она носит еще более ограничительный характер. По сути, две проблемы A и B должны почти идеально соответствовать друг другу. Существование S-редукции подразумевает существование не только строгой редукции, но и любой другой редукции, перечисленной здесь.

L-редукция

L-редукции сохраняют принадлежность как к PTAS, так и к APX (но только для задач минимизации в случае последнего ). В результате их вообще нельзя использовать для доказательства результатов о полноте APX, Log-APX или Poly-APX, но, тем не менее, они ценятся за естественность формулировки и простоту использования в доказательствах. ^[1]

PTAS-редукция

PTAS-редукция — еще одна часто используемая схема сокращения. Хотя он сохраняет членство в PTAS, он не сохраняет членство в APX. Тем не менее, APX-полнота определяется с точки зрения редукции PTAS.

PTAS-редукции являются обобщением P-редукций, показанных ниже, с той лишь разницей, что функция $g$ может зависеть от коэффициента аппроксимации $r$ .

A-редукция и P-редукция

A-редукция и P-редукция — это аналогичные схемы сокращения, которые можно использовать для отображения членства в APX и PTAS соответственно. Оба вводят новую функцию $c$ , определенную для чисел больше 1, которая должна быть вычислимой.

В A-редукции мы имеем это

R_{B}(x',y')\leq r\rightarrow R_{A}(x,y)\leq c(r)

.

В P-редукции мы имеем это

R_{B}(x',y')\leq c(r)\rightarrow R_{A}(x,y)\leq r

.

Существование P-редукции подразумевает существование PTAS-редукции.

E-редукция

E-редукция, которая является обобщением строгой редукции, но подразумевает как A-редукцию, так и P-редукцию, является примером менее ограничительного стиля редукции, который сохраняет членство не только в PTAS и APX, но и в более крупных классах Log-APX и Поли-APX . E-редукция вводит два новых параметра: полином $p$ и константу $\beta$ . Его определение следующее.

В E-редукции мы имеем это для некоторого многочлена $p$ и константы $\beta$ ,

$c_{B}({\text{OPT}}_{B}(x'))\leq p(|x|)c_{A}({\text{OPT}}_{A}(x))$ , где $|x|$ обозначает размер описания экземпляра проблемы.
Для любого решения $y'$ до $Б$ , у нас есть $R_{A}(x,y)\leq 1+\beta \cdot (R_{B}(x',y')-1)$ .

Чтобы получить A-редукцию из E-редукции, пусть $c(r)=1+\beta \cdot (r-1)$ , и чтобы получить P-редукцию из E-редукции, пусть $c(r)=1+(r-1)/\beta$ .

AP-снижение

AP-сокращения используются для определения полноты в классах Log-APX и Poly-APX . Они представляют собой частный случай сокращения PTAS и удовлетворяют следующим ограничениям.

В AP-редукции мы имеем это для некоторой постоянной $\alpha$ ,

R_{B}(x',y')\leq r\rightarrow R_{A}(x,y)\leq 1+\alpha \cdot (r-1)

с дополнительным обобщением, что функция $g$ может зависеть от коэффициента аппроксимации $r$ , как в PTAS-редукции.

AP-редукция также является обобщением E-редукции. Фактически необходимо наложить дополнительное ограничение на AP-редукцию, чтобы сохранить членство в Log-APX и Poly-APX, как это делает E-редукция: для фиксированного размера задачи время вычисления $f, g$ должно быть не увеличивающимся по мере увеличения коэффициента аппроксимации. увеличивается.

Сокращение разрыва

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

См. также

Ссылки

^ Jump up to: ^а ^б Крещенци, Пьерлуиджи (1997). «Краткое руководство по приведениям, сохраняющим аппроксимацию» . Труды по вычислительной сложности. Двенадцатая ежегодная конференция IEEE . Вашингтон, округ Колумбия: Компьютерное общество IEEE. стр. 262–. дои : 10.1109/CCC.1997.612321 . ISBN 0-8186-7907-7 . S2CID 18911241 .

[crescenzi-1] Jump up to: ^а ^б Крещенци, Пьерлуиджи (1997). «Краткое руководство по приведениям, сохраняющим аппроксимацию» . Труды по вычислительной сложности. Двенадцатая ежегодная конференция IEEE . Вашингтон, округ Колумбия: Компьютерное общество IEEE. стр. 262–. дои : 10.1109/CCC.1997.612321 . ISBN 0-8186-7907-7 . S2CID 18911241 .

[1]