FPTAS

FPTAS

FPTAS stands for fully polynomial time approximation scheme. It refers to an algorithm that can provide a solution within a certain percentage of the optimal solution value, where the percentage is determined by a fixed value. This algorithm must be able to achieve this approximation in polynomial time, meaning that the time it takes to solve the problem is proportional to the size of the input and a fixed value. A family of approximation algorithms can be considered an FPTAS if each algorithm in the family is a polynomial-time approximation algorithm that achieves a certain level of approximation and is polynomial in both the input size and the fixed value.From: Operations Planning [2019], A fully polynomial-time approximation scheme for total completion time minimization on a single machine with DeJong's learning effect and an availability constraint [2020]

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.

A fully polynomial-time approximation scheme for total completion time minimization on a single machine with DeJong's learning effect and an availability constraint

View Article

Journal Information

Published in Engineering Optimization, 2020

Mengzhuo Bai, Yufang Zhao

An algorithm is called a ρ-approximation algorithm for a minimization problem if it produces a solution that is at most ρ times as big as the optimal value, running in time that is polynomial in the input size. A family of approximation algorithms is a fully polynomial-time approximation scheme (FPTAS) if, for each , the algorithm is a -approximation algorithm that is polynomial in the input size and in . Without loss of generality, it can be assumed that .

Explore chapters and articles related to this topic

Introduction

A fully polynomial-time approximation scheme for total completion time minimization on a single machine with DeJong's learning effect and an availability constraint