уменьшение ПТАС

В теории сложности вычислений сокращение PTAS — это сокращение, сохраняющее аппроксимацию , которое часто используется для выполнения сокращений между решениями задач оптимизации . Он сохраняет то свойство, что задача имеет схему аппроксимации с полиномиальным временем (PTAS), и используется для определения полноты для определенных классов задач оптимизации, таких как APX . Условно, если существует редукция PTAS от проблемы A к проблеме B, мы пишем ${\text{A}}\leq _{\text{PTAS}}{\text{B}}$ .

При использовании обычных сокращений «много-один» за полиномиальное время , если мы можем описать сокращение от проблемы A к проблеме B, то любое решение для B за полиномиальное время может быть составлено с этим сокращением, чтобы получить решение за полиномиальное время для проблемы A. Точно так же наша цель при определении сокращений PTAS состоит в том, чтобы при сокращении PTAS от задачи оптимизации A к проблеме B можно было составить PTAS для B с сокращением, чтобы получить PTAS для проблемы A. ^[1]

Определение

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

f отображает экземпляры проблемы A в экземпляры проблемы B.
g принимает экземпляр x проблемы A, приближенное решение соответствующей проблемы $f(x)$ в B и параметр ошибки ε и дает приближенное решение x .
α отображает параметры ошибок для решений экземпляров проблемы A в параметры ошибок для решений проблемы B.
решение y Если $f(x)$ (пример задачи B) не более $1+\alpha (\epsilon )$ раз хуже оптимального решения, то соответствующее решение $g(x,y,\epsilon )$ до x (пример задачи A) не более $1+\epsilon$ раз хуже оптимального решения.

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

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

${\text{A}}\leq _{\text{PTAS}}{\text{B}}$ и ${\text{B}}\in {\text{PTAS}}\implies {\text{A}}\in {\text{PTAS}}$
${\text{A}}\leq _{\text{PTAS}}{\text{B}}$ и ${\text{A}}\not \in {\text{PTAS}}\implies {\text{B}}\not \in {\text{PTAS}}$

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

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

См. также

Ссылки

^ Jump up to: ^а ^б Крещенци, Пьерлуиджи (1997). «Краткое руководство по приведениям, сохраняющим аппроксимацию» . Труды по вычислительной сложности. Двенадцатая ежегодная конференция IEEE . Вашингтон, округ Колумбия: Компьютерное общество IEEE. стр. 262–273. дои : 10.1109/CCC.1997.612321 . ISBN 0-8186-7907-7 . S2CID 18911241 .

Инго Вегенер. Теория сложности: исследование пределов эффективных алгоритмов. ISBN 3-540-21045-8 . Глава 8, стр. 110–111. Предварительный просмотр Google Книг

[crescenzi-1] Jump up to: ^а ^б Крещенци, Пьерлуиджи (1997). «Краткое руководство по приведениям, сохраняющим аппроксимацию» . Труды по вычислительной сложности. Двенадцатая ежегодная конференция IEEE . Вашингтон, округ Колумбия: Компьютерное общество IEEE. стр. 262–273. дои : 10.1109/CCC.1997.612321 . ISBN 0-8186-7907-7 . S2CID 18911241 .

[1]