FPTAS

FPTAS

A fully polynomial-time approximation scheme (FPTAS) is a type of algorithm that provides a solution within 100% of the optimal solution value in polynomial time, where the polynomial time is a function of the problem size and a fixed positive number. The run-time of an FPTAS is polynomial in the problem size and in the fixed positive number, while the run-time of a PTAS is polynomial in the problem size for each specific fixed positive number, but might be exponential in that number. An example of an FPTAS is the one developed by Ibarra and Kim for 0/1-Knapsack Optimization.From: Operations Planning [2019], Min–max version of single-machine scheduling with generalized due dates under scenario-based uncertainty [2022], Handbook of SCHEDULING [2004]

Introduction

View Chapter

Purchase Book

Published in Joseph Y.-T. Leung, Handbook of SCHEDULING, 2004

Joseph Y.-T. Leung

In approximation of NP-hard problems, a fully polynomial-time approximation scheme (FPTAS) is the strongest possible result that one can hope for unless, of course, P=NP. It seems that all FPTASs are based on dynamic programming (DP) formulations, which always find an optimal solution, though not necessarily in polynomial time. As a first FPTAS, Sahni [45] develops a DP-based approach for approximating problem Pm∥Cmax, in which the state variables at each stage i form a set S(i) of (m-1)-tuples, representing the total workloads of the m machines. The cardinality S(i) of each such set is controlled by rounding the input data of the instance with use of an interval partitioning method. In a similar vein, Horowitz and Sahni [46] derive an FPTAS for problems Qm∥Cmax and Rm∥Cmax.

Min–max version of single-machine scheduling with generalized due dates under scenario-based uncertainty

View Article

Journal Information

Published in Engineering Optimization, 2022

Byung-Cheon Choi, Myoung-Ju Park, Kyung Min Kim

This section shows that Problem P1 with a fixed number k is weakly NP-hard and has no fully polynomial-time approximation scheme (FPTAS), while it has a polynomial-time approximation scheme (PTAS). Note that FPTAS and PTAS are approximation schemes returning approximate solution whose objective value is at most times the optimal solution for a minimization problem for a given parameter . The run-time of an FPTAS is polynomial in the problem size and in while the run-time of a PTAS is polynomial in the problem size for each specific , but might be exponential in . Finally, it is proved that the case with an arbitrary number k cannot be approximated.

Explore chapters and articles related to this topic

Introduction

Min–max version of single-machine scheduling with generalized due dates under scenario-based uncertainty