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

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

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

Термин «L-приведение» иногда используется для обозначения Шаблон:Не переведено 5 по аналогии с классом сложности L, но это совершенно другое понятиеШаблон:Уточнить.

Определение

Пусть A и B — две задачи оптимизации, а c_A и c_B — их целевые функции. Пара функций f и g является L-приведением, если выполняются все из перечисленных ниже условий:

• функции f и g можно вычислить за полиномиальное время,
• если x — экземпляр задачи A, то f(x) является экземпляром задачи B,
• если y'  — решение для f(x), то g(y' ) — решение для x,
• существует положительная константа α, такая, что

$\mathrm{O}\mathrm{P}{\mathrm{T}}_{\mathrm{B}}(f(x))\le \alpha \mathrm{O}\mathrm{P}{\mathrm{T}}_{\mathrm{A}}(x)$,

• существует положительная константа β, такая, что для любого решения y' для f(x)

$|\mathrm{O}\mathrm{P}{\mathrm{T}}_{\mathrm{A}}(x)-c_A(g(y^{\prime }))|\le \beta |\mathrm{O}\mathrm{P}{\mathrm{T}}_{\mathrm{B}}(f(x))-c_B(y^{\prime })|$.

Свойства

Связь с PTAS-приведением

L-приведение от задачи A к задаче B влечёт за собой Шаблон:Не переведено 5, если A и B являются задачами минимизации, и Шаблон:Не переведено 5, если A и B являются задачами максимизации. В обоих случаях, если задача B имеет PTAS и существует L-приведение от A к B, то A также имеет PTASШаблон:SfnШаблон:Sfn. Это позволяет использовать L-приведение вместо доказательства существования PTAS-приведения. Крещенци высказал предположение, что более естественная формулировка L-приведения, фактически, более полезна во многих случаях ввиду простоты использованияШаблон:Sfn.

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

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

$\frac{c_A(y)}{{\mathrm{O}\mathrm{P}\mathrm{T}}_A(x)}\le \frac{{\mathrm{O}\mathrm{P}\mathrm{T}}_A(x)+\beta (c_B(y^{\prime })-{\mathrm{O}\mathrm{P}\mathrm{T}}_B(x^{\prime }))}{{\mathrm{O}\mathrm{P}\mathrm{T}}_A(x)}$

После упрощения и подстановки первой формулы получим

$\frac{c_A(y)}{{\mathrm{O}\mathrm{P}\mathrm{T}}_A(x)}\le 1+\alpha \beta \left(\frac{c_B(y^{\prime })-{\mathrm{O}\mathrm{P}\mathrm{T}}_B(x^{\prime })}{{\mathrm{O}\mathrm{P}\mathrm{T}}_B(x^{\prime })}\right)$

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

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

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

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

$\frac{c_A(y)}{{\mathrm{O}\mathrm{P}\mathrm{T}}_A(x)}\ge \frac{{\mathrm{O}\mathrm{P}\mathrm{T}}_A(x)-\beta (c_B(y^{\prime })-{\mathrm{O}\mathrm{P}\mathrm{T}}_B(x^{\prime }))}{{\mathrm{O}\mathrm{P}\mathrm{T}}_A(x)}$

После упрощения и подстановки первой формулы получим

$\frac{c_A(y)}{{\mathrm{O}\mathrm{P}\mathrm{T}}_A(x)}\ge 1-\alpha \beta \left(\frac{c_B(y^{\prime })-{\mathrm{O}\mathrm{P}\mathrm{T}}_B(x^{\prime })}{{\mathrm{O}\mathrm{P}\mathrm{T}}_B(x^{\prime })}\right)$

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

Если $\frac{1}{1-\alpha \beta {\delta }^{\prime }}=1+ϵ$, то $\frac{1}{1-{\delta }^{\prime }}=1+\frac{ϵ}{\alpha \beta (1+ϵ)-ϵ}$, что соответствует требованиям PTAS-приведения, но не AP-приведения.

Другие свойства

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

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

Примеры

• Доминирующее множество: пример с α = β = 1
• Шаблон:Не переведено 5: пример с α = 1/5, β = 2

См. также

• Шаблон:Не переведено 5
• Шаблон:Не переведено 5
• Шаблон:Не переведено 5

Литература

• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга