Меню Главная Случайная статья Настройки L-приведение Материал из https://ru.wikipedia.org L-приведение (от «linear» = «линейное») — преобразование задач оптимизации, при которой линейно сохраняются свойства аппроксимации; является одним из видов сохраняющих аппроксимацию приведений[англ.]. L-приведение в изучении возможности аппроксимации задач оптимизации играет похожую роль, какую играет полиномиальное приведение[англ.] при изучении вычислительной сложности задач разрешимости. Возможность L-приведения одной задачи к другой называется L-сводимостью[1]. Термин «L-приведение» иногда используется для обозначения приведения к логарифмическому пространству[англ.] по аналогии с классом сложности L, но это совершенно другое понятие[уточнить]. Содержание 1 Определение 2 Свойства 2.1 Связь с PTAS-приведением 2.1.1 Доказательство (случай минимизации) 2.1.2 Доказательство (случай максимизации) 2.2 Другие свойства 3 Примеры 4 См. также 5 Примечания 6 Литература Определение Пусть A и B — две задачи оптимизации, а cA и cB — их целевые функции. Пара функций 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[2][3]. Это позволяет использовать L-приведение вместо доказательства существования PTAS-приведения. Крещенци высказал предположение, что более естественная формулировка L-приведения, фактически, более полезна во многих случаях ввиду простоты использования[4]. Пусть аппроксимационный коэффициент задачи B равен ${\displaystyle 1+\delta }$. Начнём с аппроксимационного коэффициента задачи A, равного ${\displaystyle {\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}}$. Можно отбросить скобки абсолютных значений в определениях L-приведения (вторая формула), поскольку A и B являются задачами минимизации. Подставим это условие в коэффициент задачи A и получим ${\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)}$ Но член в скобках правой части, фактически, равен ${\displaystyle \delta }$. Таким образом, аппроксимационный коэффициент задачи A равен ${\displaystyle 1+\alpha \beta \delta }$. А это удовлетворяет условиям AP-приведения. Пусть аппроксимационный коэффициент задачи B равен ${\displaystyle {\frac {1}{1-\delta '}}}$. Начнём с аппроксимационного коэффициента задачи A, равного ${\displaystyle {\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}}$. Можно отбросить скобки абсолютных значений во второй формуле определения L-приведения, поскольку A и B являются задачами максимизации. Подставим это условие и получим ${\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)}$ Но член в скобках правой части, фактически, равен ${\displaystyle \delta '}$. Таким образом, аппроксимационный коэффициент задачи A равен ${\displaystyle {\frac {1}{1-\alpha \beta \delta '}}}$. Если ${\displaystyle {\frac {1}{1-\alpha \beta \delta '}}=1+\epsilon }$, то ${\displaystyle {\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-приведение[англ.] Примечания Свириденко, 1998. Kann, 1992. Papadimitriou, Yannakakis, 1988. 1 2 Crescenzi, 1997, p. 262. Литература 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.