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

{\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)

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

Это отвечает условиям снижения АП.

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

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

{\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)

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

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

Другие объекты недвижимости

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

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

Примеры

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

См. также

Ссылки

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

Г. Аусиелло, П. Крещенци, Г. Гамбози, В. Канн, А. Маркетти-Спаккамела, М. Протаси. Сложность и приближение. Задачи комбинаторной оптимизации и их свойства аппроксимации. 1999, Спрингер. 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 по теории вычислений . дои : 10.1145/62212.62233 .

[crescenzi-3] Перейти обратно: ^а ^б Крещенци, Пьерлуиджи (1997). «Краткое руководство по приведениям, сохраняющим аппроксимацию» . Труды по вычислительной сложности. Двенадцатая ежегодная конференция IEEE . Вашингтон, округ Колумбия: Компьютерное общество IEEE. стр. 262–. дои : 10.1109/CCC.1997.612321 . ISBN 9780818679070 . S2CID 18911241 .

[1]

[2]

[3]