L-приведение

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

Возможность L-приведения одной задачи к другой называется L-сводимостью[1].

Термин «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[2][3]. Это позволяет использовать L-приведение вместо доказательства существования PTAS-приведения. Крещенци высказал предположение, что более естественная формулировка L-приведения, фактически, более полезна во многих случаях ввиду простоты использования[4].

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

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

{\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$ .

А это удовлетворяет условиям AP-приведения.

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

Пусть аппроксимационный коэффициент задачи 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-приведение [4]. Можно сделать вывод, что L-приведение влечёт за собой PTAS приведение из этого факта и из того, что P-приведение влечёт за собой PTAS приведение.

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

Примеры

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

См. также

MAXSNP
Сохраняющее аппроксимацию приведение
PTAS-приведение

Литература

Ausiello G., Crescenzi P., Gambosi G., Kann V., Marchetti-Spaccamela A., Protasi M. . Complexity and Approximation. Combinatorial optimization problems and their approximability properties.. — Springer, 1999. — ISBN 3-540-65431-3.
Crescenzi, Pierluigi. A Short Guide To Approximation Preserving Reductions // Proceedings of the 12th Annual IEEE Conference on Computational Complexity. — Washington, D.C., 1997.
Kann, Viggo. . On the Approximability of NP-complete \mathrm{OPT}imization Problems. — Royal Institute of Technology, Sweden, 1992. — ISBN 91-7170-082-X.
Papadimitriou C. H., Yannakakis M. . STOC '88: Proceedings of the twentieth annual ACM Symposium on Theory of Computing. — 1988. — doi:10.1145/62212.62233.
Свириденко Максим Иванович. Алгоритмы с оценками для дискретных задач размещения. — Новосибирск, 1998. — (Диссертация).

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[_1075a5449a8dd6e4-1] Свириденко, 1998.

[_0ed09568f5761e02-2] Kann, 1992.

[_df294775b5ee1bf5-3] Papadimitriou, Yannakakis, 1988.

[_a5b7e777d92b2ec9-4] Crescenzi, 1997, p. 262.