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 ,
• существует положительная константа α такая, что

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

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

${\displaystyle |\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 являются задачами минимизации. Подставьте это условие, чтобы получить ${\displaystyle 1+\delta }$ ${\displaystyle {\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}}$

${\displaystyle {\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)}}}$

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

${\displaystyle {\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 равен . ${\displaystyle \delta }$ ${\displaystyle 1+\alpha \beta \delta }$

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

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

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

${\displaystyle {\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)}}}$

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

${\displaystyle {\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 равен . ${\displaystyle \delta '}$ ${\displaystyle {\frac {1}{1-\alpha \beta \delta '}}}$

Если , то , что соответствует требованиям по снижению PTAS, но не по снижению AP. ${\displaystyle {\frac {1}{1-\alpha \beta \delta '}}=1+\epsilon }$ ${\displaystyle {\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

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

• МАКССНП
• Сокращение, сохраняющее приближение
• Сокращение ПТАС

Ссылки

1. Канн, Вигго (1992). Об аппроксимируемости NP-полных задач \mathrm{OPT}имизации . Королевский технологический институт, Швеция. ISBN 978-91-7170-082-7.
2. Христос Х. Пападимитриу; Михалис Яннакакис (1988). "\mathrm{OPT}имизация, аппроксимация и классы сложности". STOC '88: Труды двадцатого ежегодного симпозиума ACM по теории вычислений . doi : 10.1145/62212.62233 .
3. 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