Является ли схема полиномиального приближения схемой полиномиального приближения

Question

Я хочу знать, является ли схема аппроксимации, которая является схемой аппроксимации полностью за полиномиальное время, - это также схема аппроксимации за полиномиальное время?

Например, схема аппроксимации, которая работает в O (n ² (1 / ε) ³ ） - мы знаем, что это схема аппроксимации за полиномиальное время.

Это также схема аппроксимации за полиномиальное время? Спасибо!

Вот две соответствующие проблемы (Истинные или Ложные):

1. Схема аппроксимации, которая работает в O (n 2 / ϵ) для любого фиксированного ϵ> 0, является полностьюСхема аппроксимации за полиномиальное время.
2. Схема аппроксимации, которая выполняется в O (n2 (1 / ε) 3) для любого фиксированного ϵ> 0, является схемой аппроксимации за полиномиальное время.

Answer 1

Спасибо за интересный вопрос.Я провел небольшое исследование и придумал эту очень хорошую академическую лекцию о PTAS (схема аппроксимации за полиномиальное время) и полностью PTAS.

Как указано в лекции:

Время выполнения алгоритма должно быть полиномиальным по n;однако его зависимость от ε может быть экспоненциальной.Таким образом, время работы может быть O ((2 ^ (1 / ε)) * n ^ 2), например, или O (n ^ (1 / ε)), или O ((n ^ 2) / ε) и т. Д.Если зависимость от параметра 1 / ε также является полиномиальной, то мы говорим о полностью приближенной схеме полиномиального времени (FPTAS).В этой лекции мы приводим пример FPTAS.

Поскольку требование от ε в PTAS должно быть экспоненциальной зависимости, то очистка FPTAS является подслучаем PTAS, так как 1 /ε имеет полиномиальную зависимость (O (FPTAS)

Итог - FPTAS - это PTAS.