Снижение PTAS - PTAS reduction

В теория сложности вычислений, а Снижение PTAS является редукция, сохраняющая приближение что часто используется для выполнения сокращение между решениями проблемы оптимизации. Он сохраняет свойство проблемы схема аппроксимации полиномиальным временем (PTAS) и используется для определения полнота для определенных классов задач оптимизации, таких как APX. Условно, если существует редукция PTAS от проблемы A к проблеме B, мы пишем .

С обычным многочленные редукции с полиномиальным временем, если мы можем описать снижение от проблемы A к проблеме B, то любое решение за полиномиальное время для B может быть составлено с этой редукцией, чтобы получить решение за полиномиальное время для задачи A. Точно так же наша цель при определении редукций PTAS состоит в том, чтобы при заданной редукции PTAS От задачи оптимизации A к задаче B можно составить PTAS для B с редукцией, чтобы получить PTAS для задачи A.

Определение

Формально мы определяем редукцию PTAS от A до B с помощью трех вычислимых за полиномиальное время функций: ж, грамм, и α, со следующими свойствами:

  • ж сопоставляет экземпляры проблемы A с экземплярами проблемы B.
  • грамм берет пример Икс задачи А приближенное решение соответствующей задачи в B, и параметр ошибки ε и дает приближенное решение Икс.
  • α сопоставляет параметры ошибок для решений экземпляров проблемы A с параметрами ошибок для решений проблемы B.
  • Если решение у к (пример проблемы B) не более раз хуже оптимального решения, то соответствующее решение к Икс (пример проблемы A) не более раза хуже оптимального решения.

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

Из определения легко показать, что:

  • и
  • и

L-редукции подразумевают снижение PTAS. В результате вместо этого можно показать существование снижения PTAS через L-редукцию.[1]

Сокращения PTAS используются для определения полноты в APX, класс задач оптимизации с алгоритмами постоянной аппроксимации.

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

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

  1. ^ Крещенци, Пьерлуиджи (1997). «Краткое руководство по приближению с сохранением редукций». Материалы 12-й ежегодной конференции IEEE по вычислительной сложности. Вашингтон, округ Колумбия: Компьютерное общество IEEE: 262–.