L-редукция

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

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

Определение

Пусть A и B — задачи оптимизации , а c _A и c _{B —} их соответствующие функции стоимости. Пара функций f и g является L-редукцией, если выполняются все следующие условия:

Функции f и g вычислимы за полиномиальное время ,
если x является примером задачи A, то f ( x ) является примером задачи B,
если y' является решением f ( x ), то g ( y' ) является решением x ,
существует положительная константа α такая, что

\mathrm {OPT_{B}} (f(x))\leq \alpha \mathrm {OPT_{A}} (x)

,

существует положительная константа β такая, что для каждого решения y' функции f ( x )

|\mathrm {OPT_{A}} (x)-c_{A}(g(y'))|\leq \beta |\mathrm {OPT_{B}} (f(x))-c_{B}(y')|

.

Характеристики

Последствия снижения PTAS

L-редукция от задачи A к задаче B подразумевает AP-редукцию , когда A и B являются задачами минимизации, и PTAS-редукцию , когда A и B являются задачами максимизации. В обоих случаях, когда B имеет PTAS и существует L-редукция от A к B, то A также имеет PTAS. ^[1]^[2] Это позволяет использовать L-редукцию в качестве замены для демонстрации существования PTAS-редукции; Крещенци предположил, что более естественная формулировка L-редукции на самом деле более полезна во многих случаях из-за простоты использования. ^[3]

Доказательство (случай минимизации)

Пусть отношение аппроксимации B будет . Начнем с отношения аппроксимации A, . Мы можем удалить абсолютные значения вокруг третьего условия определения L-редукции, поскольку мы знаем, что A и B являются задачами минимизации. Подставьте это условие, чтобы получить $1+\delta$ ${\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}$

{\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}\leq {\frac {\mathrm {OPT} _{A}(x)+\beta (c_{B}(y')-\mathrm {OPT} _{B}(x'))}{\mathrm {OPT} _{A}(x)}}

Упрощая и подставляя первое условие, имеем

{\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}\leq 1+\alpha \beta \left({\frac {c_{B}(y')-\mathrm {OPT} _{B}(x')}{\mathrm {OPT} _{B}(x')}}\right)

Но член в скобках в правой части на самом деле равен . Таким образом, коэффициент аппроксимации A равен . $\delta$ $1+\alpha \beta \delta$

Это соответствует условиям снижения AP.

Доказательство (случай максимизации)

Пусть отношение аппроксимации B будет . Начнем с отношения аппроксимации A, . Мы можем удалить абсолютные значения вокруг третьего условия определения L-редукции, поскольку мы знаем, что A и B являются задачами максимизации. Подставьте это условие, чтобы получить ${\frac {1}{1-\delta '}}$ ${\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}$

{\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}\geq {\frac {\mathrm {OPT} _{A}(x)-\beta (c_{B}(y')-\mathrm {OPT} _{B}(x'))}{\mathrm {OPT} _{A}(x)}}

Упрощая и подставляя первое условие, имеем

{\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}\geq 1-\alpha \beta \left({\frac {c_{B}(y')-\mathrm {OPT} _{B}(x')}{\mathrm {OPT} _{B}(x')}}\right)

Но член в скобках в правой части на самом деле равен . Таким образом, коэффициент аппроксимации A равен . $\delta '$ ${\frac {1}{1-\alpha \beta \delta '}}$

Если , то , что соответствует требованиям по снижению PTAS, но не по снижению AP. ${\frac {1}{1-\alpha \beta \delta '}}=1+\epsilon$ ${\frac {1}{1-\delta '}}=1+{\frac {\epsilon }{\alpha \beta (1+\epsilon )-\epsilon }}$

Другие свойства

L-редукции также подразумевают P-редукцию . ^[3] Из этого факта и того факта, что P-редукции подразумевают PTAS-редукции, можно сделать вывод, что L-редукции подразумевают PTAS-редукции.

L-сокращения сохраняют членство в APX только для минимизирующего случая, поскольку подразумевают AP-сокращения.

Примеры

Доминирующий набор : пример с α = β = 1
Реконфигурация токена : пример с α = 1/5, β = 2

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

Ссылки

^ Канн, Вигго (1992). Об аппроксимируемости NP-полных задач \mathrm{OPT}имизации . Королевский технологический институт, Швеция. ISBN 978-91-7170-082-7.
^ Христос Х. Пападимитриу; Михалис Яннакакис (1988). "\mathrm{OPT}имизация, аппроксимация и классы сложности". STOC '88: Труды двадцатого ежегодного симпозиума ACM по теории вычислений . doi : 10.1145/62212.62233 .
^ ab Crescenzi, Pierluigi (1997). "Краткое руководство по аппроксимации сохраняющих редукций". Труды Computational Complexity. Двенадцатая ежегодная конференция IEEE . Вашингтон, округ Колумбия: IEEE Computer Society. стр. 262–. doi :10.1109/CCC.1997.612321. ISBN 9780818679070. S2CID 18911241.

G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi. Сложность и аппроксимация. Комбинаторные задачи оптимизации и их аппроксимативные свойства. 1999, Springer. ISBN 3-540-65431-3

П ≟ НП

Эта статья по теоретической информатике – заглушка . Вы можете помочь Википедии, расширив ее.

[Kann92-1] Канн, Вигго (1992). Об аппроксимируемости NP-полных задач \mathrm{OPT}имизации . Королевский технологический институт, Швеция. ISBN 978-91-7170-082-7.

[Papadimitriou88-2] Христос Х. Пападимитриу; Михалис Яннакакис (1988). "\mathrm{OPT}имизация, аппроксимация и классы сложности". STOC '88: Труды двадцатого ежегодного симпозиума ACM по теории вычислений . doi : 10.1145/62212.62233 .

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