Сокращение, сохраняющее приближение

Алгоритм преобразования одной задачи оптимизации в другую

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

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

Определение

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

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

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

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

• f отображает экземпляр x объекта A в экземпляр B.​​ ${\displaystyle x'}$
• g отображает решение B в решение y уравнения A.​​ ${\displaystyle y'}$
• g сохраняет некоторую гарантию производительности решения или коэффициента аппроксимации , определяемого как . ${\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-редукция. ^[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-редукции, для которой и оптимумы двух соответствующих экземпляров должны иметь одинаковую стоимость. S-редукция является очень частным случаем строгой редукции и является еще более ограничивающей. По сути, две проблемы A и B должны находиться в почти идеальном соответствии друг с другом. Существование S-редукции подразумевает не только существование строгой редукции, но и любой другой редукции, перечисленной здесь. ${\displaystyle c_{A}(x,y)=c_{B}(x',y')}$

L-редукция

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

PTAS-редукция

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

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

А-редукция и Р-редукция

A-редукция и P-редукция — это похожие схемы редукции, которые можно использовать для демонстрации членства в APX и PTAS соответственно. Обе вводят новую функцию 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-сокращение

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

В E-редукции мы имеем, что для некоторого полинома p и константы , ${\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}(x,y)\leq 1+\beta \cdot (R_{B}(x',y')-1)}$

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

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

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

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

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

• Сокращение (сложность)
• Сокращение ПТАС
• L-редукция
• Алгоритм аппроксимации

Ссылки

1. Crescenzi, Pierluigi (1997). "Краткое руководство по аппроксимации сохраняющих редукций". Труды Computational Complexity. Двенадцатая ежегодная конференция IEEE . Вашингтон, округ Колумбия: IEEE Computer Society. стр. 262–. doi :10.1109/CCC.1997.612321. ISBN 0-8186-7907-7. S2CID  18911241.