WikiDer > L-редукция

L-reduction

В Информатика, особенно изучение аппроксимационные алгоритмы, L-редукция ("линейная редукция") является преобразованием проблемы оптимизации который линейно сохраняет признаки аппроксимируемости; это один из видов редукция, сохраняющая приближение. L-редукции в исследованиях аппроксимируемости проблемы оптимизации играть ту же роль, что и полиномиальные редукции в исследованиях вычислительная сложность из проблемы решения.

Период, термин L сокращение иногда используется для обозначения сокращение пространства журнала, по аналогии с классом сложности L, но это другое понятие.

Определение

Пусть A и B проблемы оптимизации и cА и cB их соответствующие функции затрат. Пара функций ж и грамм является L-редукцией, если выполняются все следующие условия:

  • функции ж и грамм вычислимы в полиномиальное время,
  • если Икс является примером проблемы A, то ж(Икс) является примером проблемы B,
  • если y ' это решение ж(Икс), тогда грамм(y ' ) является решением Икс,
  • существует положительная постоянная α такая, что
,
  • существует такая положительная постоянная β, что для любого решения y ' к ж(Икс)
.

Характеристики

Последствия снижения PTAS

L-редукция от проблемы A к проблеме B влечет AP-снижение когда A и B - задачи минимизации и a Снижение PTAS когда A и B - проблемы максимизации. В обоих случаях, когда B имеет PTAS и есть L-редукция от A до B, тогда A также имеет PTAS.[1][2] Это позволяет использовать L-редукцию в качестве замены для демонстрации существования PTAS-редукции; Крещенци предположил, что более естественная формулировка L-уменьшения на самом деле более полезна во многих случаях из-за простоты использования.[3]

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

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

Упрощая и подставляя первое условие, имеем

Но член в скобках справа на самом деле равен . Таким образом, коэффициент аппроксимации A равен .

Это соответствует условиям для AP-снижения.

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

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

Упрощая и подставляя первое условие, имеем

Но член в скобках справа на самом деле равен . Таким образом, коэффициент аппроксимации A равен .

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

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

L-редукции также подразумевают P-редукция.[3] Из этого факта можно сделать вывод, что L-редукции подразумевают PTAS-сокращения, а также тот факт, что P-редукции подразумевают PTAS-сокращения.

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

Примеры

Смотрите также

Рекомендации

  1. ^ Канн, Вигго (1992). Об аппроксимируемости NP-полных задач математической {OPT} имитации. Королевский технологический институт, Швеция. ISBN 978-91-7170-082-7.
  2. ^ Христос Х. Пападимитриу; Михалис Яннакакис (1988). "mathrm {OPT} имитация, аппроксимация и классы сложности". STOC '88: Материалы двадцатого ежегодного симпозиума ACM по теории вычислений. Дои:10.1145/62212.62233.
  3. ^ а б Крещенци, Пьерлуиджи (1997). «Краткое руководство по приближению с сохранением редукций». Материалы 12-й ежегодной конференции IEEE по вычислительной сложности. Вашингтон, округ Колумбия: Компьютерное общество IEEE: 262–.
  • Г. Аузиелло, П. Крещенци, Дж. Гамбози, В. Канн, А. Маркетти-Спаккамела, М. Протаси. Сложность и приближение. Комбинаторные задачи оптимизации и их свойства аппроксимируемости. 1999 г., Springer. ISBN 3-540-65431-3