Русская Википедия:L-приведение
Шаблон:Не путать Шаблон:Не путать L-приведение (от «linear» = «линейное») — преобразование задач оптимизации, при которой линейно сохраняются свойства аппроксимации; является одним из видов Шаблон:Не переведено 5. L-приведение в изучении возможности аппроксимации задач оптимизации играет похожую роль, какую играет Шаблон:Не переведено 5 при изучении вычислительной сложности задач разрешимости.
Возможность L-приведения одной задачи к другой называется L-сводимостьюШаблон:Sfn.
Термин «L-приведение» иногда используется для обозначения Шаблон:Не переведено 5 по аналогии с классом сложности L, но это совершенно другое понятиеШаблон:Уточнить.
Определение
Пусть A и B — две задачи оптимизации, а cA и cB — их целевые функции. Пара функций f и g является L-приведением, если выполняются все из перечисленных ниже условий:
- функции f и g можно вычислить за полиномиальное время,
- если x — экземпляр задачи A, то f(x) является экземпляром задачи B,
- если y' — решение для f(x), то g(y' ) — решение для x,
- существует положительная константа α, такая, что
- <math>\mathrm{OPT_B}(f(x)) \le \alpha \mathrm{OPT_A}(x)</math>,
- существует положительная константа β, такая, что для любого решения y' для f(x)
- <math>|\mathrm{OPT_A}(x)-c_A(g(y'))| \le \beta |\mathrm{OPT_B}(f(x))-c_B(y')|</math>.
Свойства
Связь с PTAS-приведением
L-приведение от задачи A к задаче B влечёт за собой Шаблон:Не переведено 5, если A и B являются задачами минимизации, и Шаблон:Не переведено 5, если A и B являются задачами максимизации. В обоих случаях, если задача B имеет PTAS и существует L-приведение от A к B, то A также имеет PTASШаблон:SfnШаблон:Sfn. Это позволяет использовать L-приведение вместо доказательства существования PTAS-приведения. Крещенци высказал предположение, что более естественная формулировка L-приведения, фактически, более полезна во многих случаях ввиду простоты использованияШаблон:Sfn.
Доказательство (случай минимизации)
Пусть аппроксимационный коэффициент задачи B равен <math>1 + \delta</math>. Начнём с аппроксимационного коэффициента задачи A, равного <math>\frac{c_A(y)}{\mathrm{OPT}_A(x)}</math>. Можно отбросить скобки абсолютных значений в определениях L-приведения (вторая формула), поскольку A и B являются задачами минимизации. Подставим это условие в коэффициент задачи A и получим
- <math>\frac{c_A(y)}{\mathrm{OPT}_A(x)} \le \frac{\mathrm{OPT}_A(x) + \beta(c_B(y') - \mathrm{OPT}_B(x'))}{\mathrm{OPT}_A(x)}</math>
После упрощения и подстановки первой формулы получим
- <math>\frac{c_A(y)}{\mathrm{OPT}_A(x)} \le 1 + \alpha \beta \left( \frac{c_B(y')-\mathrm{OPT}_B(x')}{\mathrm{OPT}_B(x')} \right)</math>
Но член в скобках правой части, фактически, равен <math>\delta</math>. Таким образом, аппроксимационный коэффициент задачи A равен <math>1 + \alpha\beta\delta</math>.
А это удовлетворяет условиям AP-приведения.
Доказательство (случай максимизации)
Пусть аппроксимационный коэффициент задачи B равен <math>\frac{1}{1 - \delta'}</math>. Начнём с аппроксимационного коэффициента задачи A, равного <math>\frac{c_A(y)}{\mathrm{OPT}_A(x)}</math>. Можно отбросить скобки абсолютных значений во второй формуле определения L-приведения, поскольку A и B являются задачами максимизации. Подставим это условие и получим
- <math>\frac{c_A(y)}{\mathrm{OPT}_A(x)} \ge \frac{\mathrm{OPT}_A(x) - \beta(c_B(y') - \mathrm{OPT}_B(x'))}{\mathrm{OPT}_A(x)}</math>
После упрощения и подстановки первой формулы получим
- <math>\frac{c_A(y)}{\mathrm{OPT}_A(x)} \ge 1 - \alpha \beta \left( \frac{c_B(y')-\mathrm{OPT}_B(x')}{\mathrm{OPT}_B(x')} \right)</math>
Но член в скобках правой части, фактически, равен <math>\delta'</math>. Таким образом, аппроксимационный коэффициент задачи A равен <math>\frac{1}{1 - \alpha\beta\delta'}</math>.
Если <math>\frac{1}{1 - \alpha\beta\delta'} = 1+\epsilon</math>, то <math>\frac{1}{1 - \delta'} = 1 + \frac{\epsilon}{\alpha\beta(1+\epsilon) - \epsilon}</math>, что соответствует требованиям PTAS-приведения, но не AP-приведения.
Другие свойства
L-приведение также влечёт за собой Шаблон:Не переведено 5 Шаблон:Sfn. Можно сделать вывод, что L-приведение влечёт за собой PTAS приведение из этого факта и из того, что P-приведение влечёт за собой PTAS приведение.
L-приведение сохраняет членство в APX только для случая минимизации, поскольку в этом случае из L-приведения вытекает AP-приведение.
Примеры
- Доминирующее множество: пример с α = β = 1
- Шаблон:Не переведено 5: пример с α = 1/5, β = 2
См. также
Примечания
Литература
