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 which 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/ε.G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and Approximation: Combinatorial optimization problems and their approximability properties, Springer-Verlag, 1999.
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.. See discussion following Definition 1.30 on p. 20.
Relation to other complexity classes 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.
Converting a dynamic program to an FPTAS Woeginger presented a general scheme for converting a certain class of dynamic programs to an FPTAS.
Input 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.
Extremely-simple dynamic program It is assumed that the problem has a dynamic-programming (DP) algorithm using states. Each state is a vector made of some non-negative integers, where is independent of the input. The DP works in n steps. At each step i, it processes the input xi, and constructs a set of states Si. Each state encodes a partial solution to the problem, using inputs x1,...,xi. The components of the DP are:
A set S0 of initial states. A set F of transition functions. Each function f in F maps a pair (state,input) to a new state. An objective function g, mapping a state to its value.
The algorithm of the DP is:
Let S0 := the set of initial states. For k = 1 to n do: Let Sk := {f(s,xk) | f in F, s in Sk−1} Output min/max {g(s) | s in Sn}. The run-time of the DP is linear in the number of possible states. In general, this number can be exponential in the size of the input problem: it can be in O(n Vb), where V is the largest integer than can appear in a state. If V is in O(X), then the run-time is in O(n Xb), which is only pseudo-polynomial time, since it is exponential in the problem size which is in O(log X).
The way to make it polynomial is to trim the state-space: instead of keeping all possible states in each step, keep only a subset of the states; remove states that are "sufficiently close" to other states. Under certain conditions, this trimming can be done in a way that does not change the objective value by too much.
To formalize this, we assume that the problem at hand has a non-negative integer vector d = (d1,...,db), called the degree vector of the problem. For every real number r>1, we say that two state-vectors s1,s2 are (d,r)-close if, for each coordinate j in 1,...,b: (in particular, if dj=0 for some j, then ).
A problem is called extremely-benevolent if it satisfies the following three conditions:
Proximity is preserved by the transition functions: For any r>1, for any transition function f in F, for any input-vector x, and for any two state-vectors s1,s2, the following holds: if s1 is (d,r)-close to s2, then f(s1,x) is (d,r)-close to f(s2,x). A sufficient condition for this can be checked as follows. For every function f(s,x) in F, and for every coordinate j in 1,...,b, denote by fj(s,x) the j-th coordinate of f. This fj can be seen as an integer function in b+a variables. Suppose that every such fj is a polynomial with non-negative coefficients. Convert it to a polynomial of a single variable z, by substituting s=(zd1,...,zdb) and x=(1,...,1). If the degree of the resulting polynomial in z is at most dj, then condition 1 is satisfied. Proximity is preserved by the value function: There exists an integer G ≥ 0 (which is a function of the value function g and the degree vector d), such that for any r>1, and for any two state-vectors s1,s2, the following holds: if s1 is (d,r)-close to s2, then: g(s1) ≤ rG · g(s2) (in minimization problems); g(s1) ≥ r(-G) · g(s2) (in maximization problems). A sufficient condition for this is that the function g is a polynomial function (of b variables) with non-negative coefficients. Technical conditions: All transition functions f in F and the value function g can be evaluated in polytime. The number |F| of transition functions is polynomial in n and log(X). The set S0 of initial states can be computed in time polynomial in n and log(X). Let Vj be the set of all values that can appear in coordinate j in a state. Then, the ln of every value in Vj is at most a polynomial P1(n,log(X)). If dj=0, the cardinality of Vj is at most a polynomial P2(n,log(X)). For every extremely-benevolent problem, the dynamic program can be converted into an FPTAS. Define:
:= the required approximation ratio. , where G is the constant from condition 2. Note that . , where P1 is the polynomial from condition 3 (an upper bound on the ln of every value that can appear in a state vector). Note that , so it is polynomial in the size of the input and in . Also, , so by definition of P1, every integer that can appear in a state-vector is in the range [0,rL]. Partition the range [0,rL] into L+1 r-intervals: . Partition the state space into r-boxes: each coordinate k with degree dk ≥ 1 is partitioned into the L+1 intervals above; each coordinate with dk = 0 is partitioned into P2(n,log(X)) singleton intervals - an interval for each possible value of coordinate k (where P2 is the polynomial from condition 3 above). Note that every possible state is contained in exactly one r-box; if two states are in the same r-box, then they are (d,r)-close. . Note that the number of r-boxes is at most R. Since b is a fixed constant, this R is polynomial in the size of the input and in .
The FPTAS runs similarly to the DP, but in each step, it trims the state set into a smaller set Tk, that contains exactly one state in each r-box. The algorithm of the FPTAS is: Let T0 := S0 = the set of initial states. For k = 1 to n do: Let Uk := {f(s,xk) | f in F, s in Tk−1} Let Tk := a trimmed copy of Uk: for each r-box that contains one or more states of Uk, keep exactly one state in Tk. Output min/max {g(s) | s in Tn}. The run-time of the FPTAS is polynomial in the total number of possible states in each Ti, which is at most the total number of r-boxes, which is at most R, which is polynomial in n, log(X), and .
Note that, for each state su in Uk, its subset Tk contains at least one state st that is (d,r)-close to su. Also, each Uk is a subset of the Sk in the original (untrimmed) DP. The main lemma for proving the correctness of the FPTAS is: For every step k in 0,...,n, for every state ss in Sk, there is a state st in Tk that is (d,rk)-close to ss.
The proof is by induction on k. For k=0 we have Tk=Sk; every state is (d,1)-close to itself. Suppose the lemma holds for k-1. For every state ss in Sk, let ss- be one of its predecessors in Sk-1, so that f(ss−,x)=ss. By the induction assumption, there is a state st- in Tk-1, that is (d,rk-1)-close to ss−. Since proximity is preserved by transitions (Condition 1 above), f(st−,x) is (d,rk-1)-close to f(ss−,x)=ss. This f(st−,x) is in Uk. After the trimming, there is a state st in Tk that is (d,r)-close to f(st-,x). This st is (d,rk)-close to ss.
Consider now the state s* in Sn, which corresponds to the optimal solution (that is, g(s*)=OPT). By the lemma above, there is a state t* in Tn, which is (d,rn)-close to s*. Since proximity is preserved by the value function, g(t*) ≥ r(-Gn) · g(s*) for a maximization problem. By definition of r, . So . A similar argument works for a minimization problem.
Examples Here are some examples of extremely-benevolent problems, that have an FPTAS by the above theorem.
1. Multiway number partitioning (equivalently, Identical-machines scheduling) with the goal of minimizing the largest sum is extremely-benevolent. Here, we have a = 1 (the inputs are integers) and b = the number of bins (which is considered fixed). Each state is a vector of b integers representing the sums of the b bins. There are b functions: each function j represents inserting the next input into bin j. The function g(s) picks the largest element of s. S0 = {(0,...,0)}. The conditions for extreme-benevolence are satisfied with degree-vector d=(1,...,1) and G=1. The result extends to Uniform-machines scheduling and Unrelated-machines scheduling whenever the number of machines is fixed (this is required because R - the number of r-boxes - is exponential in b). Denoted Pm|| or Qm|| or Rm||.
Note: consider the special case b=2, where the goal is to minimize the square of the difference between the two part sums. The same DP can be used, but this time with value function g(s) = (s1-s2)2. Now, condition 2 is violated: the states (s1,s1) and (s1,s2) may be (d,r)-close, but g(s1,s1) = 0 while g(s1,s2) > 0. so the above theorem cannot be applied. Indeed, the problem does not have an FPTAS unless P=NP, since an FPTAS could be used to decide in polytime whether the optimal value is 0.
2. Sum of cubed job completion time on any fixed number of identical or uniform machines - the latter denoted by Qm|| - is ex-benevolent with a=1, b=3, d=(1,1,3). It can be extended to any fixed power of the completion time.
3. Sum of weighted completion time on any fixed number of identical or uniform machines - the latter denoted by Qm||.
4. Sum of completion time on any fixed number of identical or uniform machines, with time-dependent processing times: Qm|time-dep|. This holds even for weighted sum of completion time.
5. Weighted earliness-tardiness about a common due-date on any fixed number of machines: m||.
Simple dynamic program
Simple dynamic programs add to the above formulation the following components:
A set H of filtering functions, of the same cardinality as F. Each function hi in H maps a pair (state,input) to a Boolean value. The value should be "true" if and only if activating the transition fi on this pair would lead to a valid state. A dominance relation, which is a partial order on states (no indifferences, not all pairs are comparable), and a quasi-dominance relation which is a total preorder on states (indifferences allowed, all pairs are comparable). The original DP is modified as follows: Let S0 := the set of initial states. For k = 1 to n do: Let Sk := {fj(s,xk) | fj in F, s in Sk−1, hj(s,xk)=True }, where hj is the filter function corresponding to the transition function fj. Output min/max {g(s) | s in Sn}. A problem is called benevolent if it satisfies the following conditions (which extend conditions 1, 2, 3 above):