Приведение с сохранением аппроксимации - Approximation-preserving reduction

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

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

Определение

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

Позволять ${\displaystyle A}$ и ${\displaystyle B}$ быть проблемами оптимизации.

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

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

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

Типы

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

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

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

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

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

${\displaystyle R_{A}(x,y)\leq R_{B}(x',y')}$ за ${\displaystyle x'=f(x),y=g(y')}$.

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

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

L-редукция

Основная статья: L-редукция

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

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

Основная статья: Снижение PTAS

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

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

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

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

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

${\displaystyle R_{B}(x',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, но и в более крупные классы Лог-APX и Поли-APX. E-редукция вводит два новых параметра, полином ${\displaystyle p}$ и постоянный ${\displaystyle \beta }$. Его определение следующее.

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

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

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

AP-снижение

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

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

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

с дополнительным обобщением, что функция ${\displaystyle g}$ может зависеть от отношения аппроксимации ${\displaystyle r}$, как в ПТАС-редукции.

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

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

Основная статья: Сокращение разрыва

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

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

• Редукция (сложность)
• Снижение PTAS
• L-редукция
• Алгоритм приближения

Рекомендации

1. Крещенци, Пьерлуиджи (1997). «Краткое руководство по приближению с сохранением редукций». Материалы 12-й ежегодной конференции IEEE по вычислительной сложности. Вашингтон, округ Колумбия: Компьютерное общество IEEE: 262–.