Сокращение ПТАС

В теории вычислительной сложности сокращение 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. ^[1]

Определение

Формально мы определяем 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+\alpha (\epsilon )}$ ${\displaystyle g(x,y,\epsilon )}$ ${\displaystyle 1+\epsilon }$

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

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

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

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

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

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

• Сокращение, сохраняющее приближение
• L-редукция
• АПХ

Ссылки

1. Crescenzi, Pierluigi (1997). "Краткое руководство по аппроксимации сохраняющих сокращений". Труды Computational Complexity. Двенадцатая ежегодная конференция IEEE . Вашингтон, округ Колумбия: IEEE Computer Society. стр. 262–273. doi :10.1109/CCC.1997.612321. ISBN 0-8186-7907-7. S2CID  18911241.

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