Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Fully polynomial-time approximation scheme
Summary
A fully polynomial-time approximation scheme (FPTAS) is an algorithm for finding approximate solutions to function problems, especially optimization problems. An FPTAS takes as input an instance of the problem and a parameter ε > 0. It returns as output a value is at least times the correct value, and at most times the correct value.
In the context of optimization problems, the correct value is understood to be the value of the optimal solution, and it is often implied that an FPTAS should produce a valid solution (and not just the value of the solution). Returning a value and finding a solution with that value are equivalent assuming that the problem possesses self reducibility.
Importantly, the run-time of an FPTAS is polynomial in the problem size and in 1/ε. This is in contrast to a general polynomial-time approximation scheme (PTAS). The run-time of a general PTAS is polynomial in the problem size for each specific ε, but might be exponential in 1/ε.
The term FPTAS may also be used to refer to the class of problems that have an FPTAS. FPTAS is a subset of PTAS, and unless P = NP, it is a strict subset.
All problems in FPTAS are fixed-parameter tractable with respect to the standard parameterization.
Any strongly NP-hard optimization problem with a polynomially bounded objective function cannot have an FPTAS unless P=NP. However, the converse fails: e.g. if P does not equal NP, knapsack with two constraints is not strongly NP-hard, but has no FPTAS even when the optimal objective is polynomially bounded.
Woeginger presented a general scheme for converting a certain class of dynamic programs to an FPTAS.
The scheme handles optimization problems in which the input is defined as follows:
The input is made of n vectors, x1,...,xn.
Each input vector is made of some non-negative integers, where may depend on the input.
All components of the input vectors are encoded in binary. So the size of the problem is O(n+log(X)), where X is the sum of all components in all vectors.
It is assumed that the problem has a dynamic-programming (DP) algorithm using states.
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.