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

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

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

Термин «L-приведение» иногда используется для обозначения  по аналогии с классом сложности 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 влечёт за собой , если A и B являются задачами минимизации, и , если A и B являются задачами максимизации. В обоих случаях, если задача B имеет PTAS и существует L-приведение от A к B, то A также имеет PTAS. Это позволяет использовать L-приведение вместо доказательства существования PTAS-приведения. Крещенци высказал предположение, что более естественная формулировка L-приведения, фактически, более полезна во многих случаях ввиду простоты использования.

Доказательство (случай минимизации) 
Пусть аппроксимационный коэффициент задачи B равен .
Начнём с аппроксимационного коэффициента задачи A, равного .
Можно отбросить скобки абсолютных значений в определениях L-приведения (вторая формула), поскольку A и B являются задачами минимизации. Подставим это условие в коэффициент задачи A и получим
 
После упрощения и подстановки первой формулы получим
 
Но член в скобках правой части, фактически, равен . Таким образом, аппроксимационный коэффициент задачи A равен .

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

Доказательство (случай максимизации) 
Пусть аппроксимационный коэффициент задачи B равен .
Начнём с аппроксимационного коэффициента задачи A, равного .
Можно отбросить скобки абсолютных значений во второй формуле определения L-приведения, поскольку A и B являются задачами максимизации. Подставим это условие и получим
 
После упрощения и подстановки первой формулы получим
 
Но член в скобках правой части, фактически, равен . Таким образом, аппроксимационный коэффициент задачи A равен .

Если , то , что соответствует требованиям PTAS-приведения, но не AP-приведения.

Другие свойства 
L-приведение также влечёт за собой  . Можно сделать вывод, что L-приведение влечёт за собой PTAS приведение из этого факта и из того, что P-приведение влечёт за собой PTAS приведение.

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

Примеры 
 Доминирующее множество: пример с α = β = 1
 : пример с α = 1/5, β = 2

См. также

Примечания

Литература 
 
 
 
 
 

Теория сложности вычислений
Аппроксимационные алгоритмы