Input

The scheme handles optimization problems in which the input is defined as follows:

• The input is made of n vectors, x₁,...,x_n.
• Each input vector is made of some ${\displaystyle a}$ non-negative integers, where ${\displaystyle a}$ 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 ${\displaystyle b}$ non-negative integers, where ${\displaystyle b}$ is independent of the input. The DP works in n steps. At each step i, it processes the input x_i, and constructs a set of states S_i. Each state encodes a partial solution to the problem, using inputs x₁,...,x_i. The components of the DP are:

• A set S₀ 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 S₀ := the set of initial states.
• For k = 1 to n do:
  • Let S_k := {f(s,x_k) | f in F, s in S_k−1}
• Output min/max {g(s) | s in S_n}.

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 V^b), 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 X^b), 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 = (d₁,...,d_b), called the degree vector of the problem. For every real number r>1, we say that two state-vectors s₁,s₂ are (d,r)-close if, for each coordinate j in 1,...,b: ${\displaystyle r^{-d_{j}}\cdot s_{1,j}\leq s_{2,j}\leq r^{d_{j}}\cdot s_{1,j}}$ (in particular, if d_j=0 for some j, then ${\displaystyle s_{1,j}=s_{2,j}}$).

A problem is called extremely-benevolent if it satisfies the following three conditions:

1. 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 s₁,s₂, the following holds: if s₁ is (d,r)-close to s₂, then f(s₁,x) is (d,r)-close to f(s₂,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 f_j(s,x) the j-th coordinate of f. This f_j can be seen as an integer function in b+a variables. Suppose that every such f_j is a polynomial with non-negative coefficients. Convert it to a polynomial of a single variable z, by substituting s=(z^d1,...,z^db) and x=(1,...,1). If the degree of the resulting polynomial in z is at most d_j, then condition 1 is satisfied.
2. 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 s₁,s₂, the following holds: if s₁ is (d,r)-close to s₂, then: g(s₁) ≤ r^G · g(s₂) (in minimization problems); g(s₁) ≥ r^(-G) · g(s₂) (in maximization problems).
   • A sufficient condition for this is that the function g is a polynomial function (of b variables) with non-negative coefficients.
3. 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 S₀ of initial states can be computed in time polynomial in n and log(X).
   • Let V_j be the set of all values that can appear in coordinate j in a state. Then, the ln of every value in V_j is at most a polynomial P₁(n,log(X)).
   • If d_j=0, the cardinality of V_j is at most a polynomial P₂(n,log(X)).

For every extremely-benevolent problem, the dynamic program can be converted into an FPTAS. Define:

• ${\displaystyle \epsilon }$ := the required approximation ratio.
• ${\displaystyle r:=1+{\frac {\epsilon }{2Gn}}}$, where G is the constant from condition 2. Note that ${\displaystyle {\frac {1}{\ln {r}}}\leq 1+{\frac {2Gn}{\epsilon }}}$.
• ${\displaystyle L:=\left\lceil {\frac {P_{1}(n,\log(X))}{\ln(r)}}\right\rceil }$, where P₁ is the polynomial from condition 3 (an upper bound on the ln of every value that can appear in a state vector). Note that ${\displaystyle L\leq \left\lceil \left(1+{\frac {2Gn}{\epsilon }}\right)P_{1}(n,\log {X})\right\rceil }$, so it is polynomial in the size of the input and in ${\displaystyle 1/\epsilon }$. Also, ${\displaystyle r^{L}=e^{\ln {r}}\cdot L\geq e^{P_{1}(n,\log {x})}}$, so by definition of P₁, every integer that can appear in a state-vector is in the range [0,r^L].
• Partition the range [0,r^L] into L+1 r-intervals: ${\displaystyle I_{0}=[0];I_{1}=[1,r);I_{2}=[r,r^{2});\ldots ;I_{L}=[r^{L-1},r^{L}]}$.
• Partition the state space into r-boxes: each coordinate k with degree d_k ≥ 1 is partitioned into the L+1 intervals above; each coordinate with d_k = 0 is partitioned into P₂(n,log(X)) singleton intervals - an interval for each possible value of coordinate k (where P₂ 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.
• ${\displaystyle R:=(L+1+P_{2}(n,\log {X}))^{b}}$.
  • 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 ${\displaystyle 1/\epsilon }$.

The FPTAS runs similarly to the DP, but in each step, it trims the state set into a smaller set T_k, that contains exactly one state in each r-box. The algorithm of the FPTAS is:

• Let T₀ := S₀ = the set of initial states.
• For k = 1 to n do:
  • Let U_k := {f(s,x_k) | f in F, s in T_k−1}
  • Let T_k := a trimmed copy of U_k: for each r-box that contains one or more states of U_k, keep exactly one state in T_k.
• Output min/max {g(s) | s in T_n}.

The run-time of the FPTAS is polynomial in the total number of possible states in each T_i, which is at most the total number of r-boxes, which is at most R, which is polynomial in n, log(X), and ${\displaystyle 1/\epsilon }$.

Note that, for each state s_u in U_k, its subset T_k contains at least one state s_t that is (d,r)-close to s_u. Also, each U_k is a subset of the S_k in the original (untrimmed) DP. The main lemma for proving the correctness of the FPTAS is:^{[6]: Lem.3.3}

For every step k in 0,...,n, for every state s_s in S_k, there is a state s_t in T_k that is (d,r^k)-close to s_s.

The proof is by induction on k. For k=0 we have T_k=S_k; every state is (d,1)-close to itself. Suppose the lemma holds for k-1. For every state s_s in S_k, let s_s- be one of its predecessors in S_k-1, so that f(s_s−,x)=s_s. By the induction assumption, there is a state s_t- in T_k-1, that is (d,r^k-1)-close to s_s−. Since proximity is preserved by transitions (Condition 1 above), f(s_t−,x) is (d,r^k-1)-close to f(s_s−,x)=s_s. This f(s_t−,x) is in U_k. After the trimming, there is a state s_t in T_k that is (d,r)-close to f(s_t-,x). This s_t is (d,r^k)-close to s_s.

Consider now the state s^* in S_n, which corresponds to the optimal solution (that is, g(s*)=OPT). By the lemma above, there is a state t* in T_n, which is (d,rⁿ)-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, ${\displaystyle r^{-Gn}\geq (1-\epsilon )}$. So ${\displaystyle g(t^{*})\geq (1-\epsilon )\cdot OPT}$. A similar argument works for a minimization problem.

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 h_i in H maps a pair (state,input) to a Boolean value. The value should be "true" if and only if activating the transition f_i 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 S₀ := the set of initial states.
• For k = 1 to n do:
  • Let S_k := {f_j(s,x_k) | f_j in F, s in S_k−1, h_j(s,x_k)=True }, where h_j is the filter function corresponding to the transition function f_j.
• Output min/max {g(s) | s in S_n}.

A problem is called benevolent if it satisfies the following conditions (which extend conditions 1, 2, 3 above):

1. 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 s₁,s₂, the following holds:
   • if s₁ is (d,r)-close to s₂, and s₁ quasi-dominates s₂, then either (a) f(s₁,x) is (d,r)-close to f(s₂,x), and f(s₁,x) quasi-dominates f(s₂,x), or (b) f(s₁,x) dominates f(s₂,x).
   • if s₁ dominates s₂, then f(s₁,x) dominates f(s₂,x).
2. Proximity is preserved by the value function: There exists an integer G ≥ 0 (a function of the value function g and the degree vector d), such that for any r>1, and for any two state-vectors s₁,s₂, the following holds:
   • if s₁ is (d,r)-close to s₂, and s₁ quasi-dominates s₂, then: g(s₁) ≤ r^G · g(s₂) (in minimization problems); g(s₁) ≥ r^(-G) · g(s₂) (in maximization problems).
   • if s₁ dominates s₂, then g(s₁) ≤ g(s₂) (in minimization problems); g(s₁) ≥ g(s₂) (in maximization problems).
3. Technical conditions (in addition to the above):
   • The quasi-dominance relation can be decided in polynomial time.
4. Conditions on the filter functions: For any r>1, for any filter function h in H, for any input-vector x, and for any two state-vectors s₁,s₂, the following holds:
   • if s₁ is (d,r)-close to s₂, and s₁ quasi-dominates s₂, then h(s₁,x) ≥ h(s₂,x).
   • if s₁ dominates s₂, then h(s₁,x) ≥ h(s₂,x).

For every benevolent problem, the dynamic program can be converted into an FPTAS similarly to the one above, with two changes (boldfaced):

• Let T₀ := S₀ = the set of initial states.
• For k = 1 to n do:
  • Let U_k := {f_j(s,x_k) | f_j in F, s in T_k−1, h_j(s,x_k)=True }, where h_j is the filter function corresponding to the transition function f_j.
  • Let T_k := a trimmed copy of U_k: for each r-box that contains one or more states of U_k, choose a single element that quasi-dominates all other elements in U_k, and insert it into T_k.
• Output min/max {g(s) | s in T_n}.

Non-examples

Despite the generality of the above result, there are cases in which it cannot be used.

1. In the total tardiness problem 1||${\displaystyle \sum T_{j}}$, the dynamic programming formulation of Lawler^[10] requires to update all states in the old state space some B times, where B is of the order of X (the maximum input size). The same is true for a DP for economic lot-sizing.^[11] In these cases, the number of transition functions in F is B, which is exponential in the log(X), so the second technical condition is violated. The state-trimming technique is not useful, but another technique - input-rounding - has been used to design an FPTAS.^[12][13]

2. In the variance minimization problem 1||${\displaystyle CTV}$, the objective function is ${\displaystyle g(s)=s_{5}-(s_{4}-s_{3})^{2}/n}$, which violates Condition 2, so the theorem cannot be used. But different techniques have been used to design an FPTAS.^[14][15]