Приведение с сохранением приближения - Approximation-preserving reduction

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

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

Определение

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

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

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

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

$е$ сопоставляет экземпляр $х$ из $А$ к примеру из $B$ . ${\ displaystyle x '}$
$г$ отображает решение о $B$ к раствору $у$ из $A$ . ${\ displaystyle y '}$
$г$ сохраняет некоторую гарантию решения по производительности , или отношение аппроксимации , определяемое как . ${\ displaystyle 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-сокращение. Приведенные ниже описания редукций взяты из обзора редукций, сохраняющих приближение, Крещенци.

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

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

{\ Displaystyle R_ {A} (х, у) \ leq R_ {B} (х ', у')}

для .

{\ Displaystyle х '= е (х), у = г (у')}

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

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

L-редукция

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

ПТАС-редукция

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

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

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

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

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

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

.

В P-редукции имеем

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

.

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

Электронное сокращение

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

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

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

Чтобы получить A-редукцию из E-редукции, пусть , и для получения P-редукции из E-редукции, пусть . ${\ Displaystyle с (г) = 1 + \ бета \ cdot (г-1)}$ ${\ Displaystyle с (г) = 1 + (г-1) / \ бета}$

AP-снижение

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

В AP-редукции у нас есть это для некоторой константы , ${\ displaystyle \ alpha}$

{\ Displaystyle 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 не$ должно увеличиваться как коэффициент аппроксимации увеличивается.

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

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

Languages

In other projects