L-приведение (от «linear» = «линейное») — преобразование задач оптимизации, при которой линейно сохраняются свойства аппроксимации; является одним из видов сохраняющих аппроксимацию приведений[en]. L-приведение в изучении возможности аппроксимации задач оптимизации играет похожую роль, какую играет полиномиальное приведение[en] при изучении вычислительной сложности задач разрешимости.
Возможность L-приведения одной задачи к другой называется L-сводимостью[1].
Термин «L-приведение» иногда используется для обозначения приведения к логарифмическому пространству[en] по аналогии с классом сложности L, но это совершенно другое понятие[уточнить].
Определение
Пусть A и B — две задачи оптимизации, а cA и cB — их целевые функции. Пара функций f и g является L-приведением, если выполняются все из перечисленных ниже условий:
- функции f и g можно вычислить за полиномиальное время,
- если x — экземпляр задачи A, то f(x) является экземпляром задачи B,
- если y' — решение для f(x), то g(y' ) — решение для x,
- существует положительная константа α, такая, что
- ,
- существует положительная константа β, такая, что для любого решения y' для f(x)
- .
Свойства
Связь с PTAS-приведением
L-приведение от задачи A к задаче B влечёт за собой AP-приведение[en], если A и B являются задачами минимизации, и PTAS приведение[en], если A и B являются задачами максимизации. В обоих случаях, если задача B имеет PTAS и существует L-приведение от A к B, то A также имеет PTAS[2][3]. Это позволяет использовать L-приведение вместо доказательства существования PTAS-приведения. Крещенци высказал предположение, что более естественная формулировка L-приведения, фактически, более полезна во многих случаях ввиду простоты использования[4].
Доказательство (случай минимизации)
Пусть аппроксимационный коэффициент задачи B равен . Начнём с аппроксимационного коэффициента задачи A, равного . Можно отбросить скобки абсолютных значений в определениях L-приведения (вторая формула), поскольку A и B являются задачами минимизации. Подставим это условие в коэффициент задачи A и получим
После упрощения и подстановки первой формулы получим
Но член в скобках правой части, фактически, равен . Таким образом, аппроксимационный коэффициент задачи A равен .
А это удовлетворяет условиям AP-приведения.
Доказательство (случай максимизации)
Пусть аппроксимационный коэффициент задачи B равен . Начнём с аппроксимационного коэффициента задачи A, равного . Можно отбросить скобки абсолютных значений во второй формуле определения L-приведения, поскольку A и B являются задачами максимизации. Подставим это условие и получим
После упрощения и подстановки первой формулы получим
Но член в скобках правой части, фактически, равен . Таким образом, аппроксимационный коэффициент задачи A равен .
Если , то , что соответствует требованиям PTAS-приведения, но не AP-приведения.
Другие свойства
L-приведение также влечёт за собой P-приведение[en] [4]. Можно сделать вывод, что L-приведение влечёт за собой PTAS приведение из этого факта и из того, что P-приведение влечёт за собой PTAS приведение.
L-приведение сохраняет членство в APX только для случая минимизации, поскольку в этом случае из L-приведения вытекает AP-приведение.
Примеры
- Доминирующее множество: пример с α = β = 1
- Задача реконфигурации маркеров[en]: пример с α = 1/5, β = 2
См. также
Примечания
Литература
- 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. — (Диссертация).
 | Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .