Fully polynomial-time approximation scheme

A fully polynomial-time approximation scheme, abbreviated FPTAS, is an algorithm for finding approximate solutions to function problems, especially optimization problems. An FPTAS takes as input an instance of the problem together with a parameter epsilon greater than zero. It returns a value that is within a bounded factor of the correct value: at least a lower multiple of the correct value and at most an upper multiple of it, with both factors set by epsilon. The word fully refers to the requirement, part of the standard definition of the term, that the running time be polynomial in the input size and in the reciprocal of epsilon, so accuracy can be traded for time smoothly.