Схема аппроксимации с полным полиномиальным временем (FPTAS) — это алгоритм нахождения приближенно-оптимальных решений задач оптимизации . FPTAS принимает на вход экземпляр задачи и параметр ε > 0. На выходе он возвращает решение, значение которого равно -
Важно отметить, что время выполнения FPTAS полиномиально по размеру задачи и по 1/ε. Это отличается от общей схемы аппроксимации полиномиального времени (PTAS). Время выполнения общей PTAS полиномиально по размеру задачи для каждого конкретного ε, но может быть экспоненциальным по 1/ε. [1]
Термин FPTAS также может использоваться для обозначения класса задач оптимизации, в которых есть FPTAS. FPTAS — это подмножество PTAS, и если P = NP , то это строгое подмножество. [2]
Все проблемы в FPTAS решаются с фиксированными параметрами относительно стандартной параметризации. [3]
Любая сильно NP-трудная задача оптимизации с полиномиально ограниченной целевой функцией не может иметь FPTAS, если только P=NP. [4] Однако обратное неверно: например, если P не равно NP, рюкзак с двумя ограничениями не является строго NP-трудным, но не имеет FPTAS, даже когда оптимальная цель полиномиально ограничена. [5]
Woeginger [6] представил общую схему преобразования определенного класса динамических программ в FPTAS.