Снижение PTAS

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

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

Определение [ править ]

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

f отображает экземпляры проблемы A в экземпляры проблемы B.
g берет экземпляр x задачи A, приближенное решение соответствующей проблемы в B и параметр ошибки ε и дает приближенное решение x . ${\ displaystyle f (x)}$
α отображает параметры ошибок для решений экземпляров проблемы A в параметры ошибок для решений проблемы B.
Если решение y для (экземпляр проблемы B) в большинстве раз хуже, чем оптимальное решение, то соответствующее решение для x (экземпляр проблемы A) в большинстве раз хуже, чем оптимальное решение. ${\ displaystyle f (x)}$ ${\ Displaystyle 1+ \ альфа (\ эпсилон)}$ ${\ Displaystyle г (х, у, \ эпсилон)}$ $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 , классе задач оптимизации с алгоритмами аппроксимации с постоянным коэффициентом.

См. Также [ править ]

Ссылки [ править ]

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

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

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

[1]