Fully polynomial-time approximation scheme

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 ${\displaystyle 1-\varepsilon }$ times the correct value, and at most ${\displaystyle 1+\varepsilon }$ 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/ε.^[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.^[2]

Relation to other complexity classes

All problems in FPTAS are fixed-parameter tractable with respect to the standard parameterization.^[3]

Any strongly NP-hard optimization problem with a polynomially bounded objective function cannot have an FPTAS unless P=NP.^[4] 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.^[5]

Converting a dynamic program to an FPTAS

Woeginger^[6] 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, 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.

Examples

Here are some examples of extremely-benevolent problems, that have an FPTAS by the above theorem.^[6]

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. S₀ = {(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||${\displaystyle \max C_{j}}$  or Qm||${\displaystyle \max C_{j}}$  or Rm||${\displaystyle \max C_{j}}$ .

• 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) = (s₁-s₂)². Now, condition 2 is violated: the states (s₁,s₁) and (s₁,s₂) may be (d,r)-close, but g(s₁,s₁) = 0 while g(s₁,s₂) > 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||${\displaystyle \sum C_{j}^{3}}$  - 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||${\displaystyle \sum w_{j}C_{j}}$ .

4. Sum of completion time on any fixed number of identical or uniform machines, with time-dependent processing times: Qm|time-dep|${\displaystyle \sum C_{j}}$ . 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||${\displaystyle \sum w_{j}|C_{j}|}$ .

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}.

Examples

Here are some examples of benevolent problems, that have an FPTAS by the above theorem.^[6]

1. The 0-1 knapsack problem is benevolent. Here, we have a=2: each input is a 2-vector (weight, value). There is a DP with b=2: each state encodes (current weight, current value). There are two transition functions: f₁ corresponds to adding the next input item, and f₂ corresponds to not adding it. The corresponding filter functions are: h₁ verifies that the weight with the next input item is at most the knapsack capacity; h₂ always returns True. The value function g(s) returns s₂. The initial state-set is {(0,0)}. The degree vector is (1,1). The dominance relation is trivial. The quasi-dominance relation compares only the weight coordinate: s quasi-dominates t iff s₁ ≤ t₁. The implication of this is that, if state t has a higher weight than state s, then the transition functions are allowed to not preserve the proximity between t and s (it is possible, for example, that s has a successor and t does not have a corresponding successor). A similar algorithm was presented earlier by Ibarra and Kim.^[7] The run-time of this FPTAS can be improved to ${\displaystyle O(n\log {1/\epsilon }+1/\epsilon ^{4})}$  operations on integers.^[8] The exponent was later improved to 2.5.^[9]

• Note: consider In the 2-weighted knapsack problem, where each item has two weights and a value, and the goal is to maximize the value such that the sum of squares of the total weights is at most the knapsack capacity: ${\displaystyle \left(\sum _{k\in K}w_{1,k}\right)^{2}+\left(\sum _{k\in K}w_{2,k}\right)^{2}\leq W}$ . We could solve it using a similar DP, where each state is (current weight 1, current weight 2, value). The quasi-dominance relation should be modified to: s quasi-dominates t iff (s₁² + s₂²) ≤ (t₁² + t₂²). But it violates Condition 1 above: quasi-dominance is not preserved by transition functions [for example, the state (2,2,..) quasi-dominates (1,3,..); but after adding the input (2,0,..) to both states, the result (4,2,..) does not quasi-dominate (3,3,..)]. So the theorem cannot be used. Indeed, this problem does not have an FPTAS unless P=NP. The same is true for the two-dimensional knapsack problem. The same is true for the multiple subset sum problem: the quasi-dominance relation should be: s quasi-dominates t iff max(s_1,s₂) ≤ max(t_1,t₂), but it is not preserved by transitions, by the same example as above.

2. Minimizing the weighted number of tardy jobs, or maximizing the weighted number of early jobs, on a single machine; denoted 1||${\displaystyle \sum w_{j}U_{j}}$ .

3. Batch scheduling for minimizing the weighted number of tardy jobs: 1|batch|${\displaystyle \sum w_{j}U_{j}}$ .

4. Makespan of deteriorating jobs on a single machine: 1|deteriorate|${\displaystyle \max C_{j}}$ .

5. Total late work on a single machine: 1||${\displaystyle \sum V_{j}}$ .

6. Total weighted late work on a single machine: 1||${\displaystyle \sum w_{j}V_{j}}$ .

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]

FPTAS for approximating real numbers

A different kind of problems in which FPTAS may be useful is finding rational numbers that approximate some real numbers. For example, consider the infinite series ${\displaystyle \sum _{i=1}^{\infty }{\frac {1}{i^{3}}}}$ . The sum is an irrational number. To approximate it by a rational number, we can compute the sum of the first k elements, for some finite k. One can show that the error in approximation is about ${\displaystyle {\frac {1}{2k^{2}}}}$ . Therefore, to get an error of ε, we need about ${\displaystyle {\sqrt {\frac {1}{2\epsilon }}}}$  elements, so this is an FPTAS. Note that this particular sum can be represented by another sum in which only O(log(ε)) elements are needed, so the sum can actually be approximated in polynomial time in the encoding length of ε.^{[16]: 35, Sec.1}

Some other problems that have an FPTAS

• The knapsack problem,^[17][18] as well as some of its variants:
  • 0-1 knapsack problem.^[19]
  • Unbounded knapsack problem.^[20]
  • Multi-dimensional knapsack problem with Delta-modular constraints.^[21]
  • Multi-objective 0-1 knapsack problem.^[22]
  • Parametric knapsack problem.^[23]
  • Symmetric quadratic knapsack problem.^[24]
• Count-subset-sum (#SubsetSum) - finding the number of distinct subsets with a sum of at most C.^[25]
• Restricted shortest path: finding a minimum-cost path between two nodes in a graph, subject to a delay constraint.^[26]
• Shortest paths and non-linear objectives.^[27]
• Counting edge-covers.^[28]
• Vector subset search problem where the dimension is fixed.^[29]

See also

• The "benevolent dynamic programs", that admit an FPTAS, also admit an evolutionary algorithm.^[30]

References

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.
2. Jansen, Thomas (1998), "Introduction to the Theory of Complexity and Approximation Algorithms", in Mayr, Ernst W.; Prömel, Hans Jürgen; Steger, Angelika (eds.), Lectures on Proof Verification and Approximation Algorithms, Springer, pp. 5–28, doi:10.1007/BFb0053011, ISBN 9783540642015. See discussion following Definition 1.30 on p. 20.
3. Cai, Liming; Chen, Jianer (June 1997). "On Fixed-Parameter Tractability and Approximability of NP Optimization Problems". Journal of Computer and System Sciences. 54 (3): 465–474. doi:10.1006/jcss.1997.1490.
4. Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. Corollary 8.6. ISBN 3-540-65367-8.
5. H. Kellerer; U. Pferschy; D. Pisinger (2004). Knapsack Problems. Springer. Theorem 9.4.1.
6. Woeginger, Gerhard J. (2000-02-01). "When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?". INFORMS Journal on Computing. 12 (1): 57–74. doi:10.1287/ijoc.12.1.57.11901. ISSN 1091-9856.
7. Ibarra, Oscar H.; Kim, Chul E. (1975-10-01). "Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems". Journal of the ACM. 22 (4): 463–468. doi:10.1145/321906.321909. ISSN 0004-5411. S2CID 14619586.
8. Lawler, Eugene L. (1979-11-01). "Fast Approximation Algorithms for Knapsack Problems". Mathematics of Operations Research. 4 (4): 339–356. doi:10.1287/moor.4.4.339. ISSN 0364-765X. S2CID 7655435.
9. Rhee, Donguk (2015). Faster fully polynomial approximation schemes for Knapsack problems (Thesis thesis). Massachusetts Institute of Technology. hdl:1721.1/98564.
10. Lawler, Eugene L. (1977-01-01), Hammer, P. L.; Johnson, E. L.; Korte, B. H.; Nemhauser, G. L. (eds.), "A "Pseudopolynomial" Algorithm for Sequencing Jobs to Minimize Total Tardiness**Research supported by National Science Foundation Grant GJ-43227X", Annals of Discrete Mathematics, Studies in Integer Programming, vol. 1, Elsevier, pp. 331–342, doi:10.1016/S0167-5060(08)70742-8, retrieved 2021-12-17
11. Florian, M.; Lenstra, J. K.; Rinnooy Kan, A. H. G. (1980-07-01). "Deterministic Production Planning: Algorithms and Complexity". Management Science. 26 (7): 669–679. doi:10.1287/mnsc.26.7.669. ISSN 0025-1909.
12. Lawler, E. L. (1982-12-01). "A fully polynomial approximation scheme for the total tardiness problem". Operations Research Letters. 1 (6): 207–208. doi:10.1016/0167-6377(82)90022-0. ISSN 0167-6377.
13. van Hoesel, C. P. M.; Wagelmans, A. P. M. (2001). "Fully Polynomial Approximation Schemes for Single-Item Capacitated Economic Lot-Sizing Problems". Mathematics of Operations Research. 26 (2): 339–357. doi:10.1287/moor.26.2.339.10552.
14. Cai, X. (1995-09-21). "Minimization of agreeably weighted variance in single machine systems". European Journal of Operational Research. 85 (3): 576–592. doi:10.1016/0377-2217(93)E0367-7. ISSN 0377-2217.
15. Woeginger, Gerhard J. (1999-05-01). "An Approximation Scheme for Minimizing Agreeably Weighted Variance on a Single Machine". INFORMS Journal on Computing. 11 (2): 211–216. doi:10.1287/ijoc.11.2.211. ISSN 1091-9856.
16. Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419
17. Vazirani, Vijay (2001). Approximation algorithms. Berlin: Springer. pp. 69–70. ISBN 3540653678. OCLC 47097680.
18. Kellerer, Hans; Pferschy, Ulrich (2004-03-01). "Improved Dynamic Programming in Connection with an FPTAS for the Knapsack Problem". Journal of Combinatorial Optimization. 8 (1): 5–11. doi:10.1023/B:JOCO.0000021934.29833.6b. ISSN 1573-2886. S2CID 36474745.
19. Jin, Ce (2019). An Improved FPTAS for 0-1 Knapsack. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 132. pp. 76:1–76:14. arXiv:1904.09562. doi:10.4230/LIPIcs.ICALP.2019.76. ISBN 9783959771092. S2CID 128317990.
20. Jansen, Klaus; Kraft, Stefan E. J. (2018-02-01). "A faster FPTAS for the Unbounded Knapsack Problem". European Journal of Combinatorics. Combinatorial Algorithms, Dedicated to the Memory of Mirka Miller. 68: 148–174. arXiv:1504.04650. doi:10.1016/j.ejc.2017.07.016. ISSN 0195-6698. S2CID 9557898.
21. Gribanov, D. V. (2021-05-10). "An FPTAS for the $$\var Delta $$-Modular Multidimensional Knapsack Problem". Mathematical Optimization Theory and Operations Research. Lecture Notes in Computer Science. Vol. 12755. pp. 79–95. arXiv:2103.07257. doi:10.1007/978-3-030-77876-7_6. ISBN 978-3-030-77875-0. S2CID 232222954.
22. Bazgan, Cristina; Hugot, Hadrien; Vanderpooten, Daniel (2009-10-01). "Implementing an efficient fptas for the 0–1 multi-objective knapsack problem". European Journal of Operational Research. 198 (1): 47–56. doi:10.1016/j.ejor.2008.07.047. ISSN 0377-2217.
23. Holzhauser, Michael; Krumke, Sven O. (2017-10-01). "An FPTAS for the parametric knapsack problem". Information Processing Letters. 126: 43–47. arXiv:1701.07822. doi:10.1016/j.ipl.2017.06.006. ISSN 0020-0190. S2CID 1013794.
24. Xu, Zhou (2012-04-16). "A strongly polynomial FPTAS for the symmetric quadratic knapsack problem". European Journal of Operational Research. 218 (2): 377–381. doi:10.1016/j.ejor.2011.10.049. hdl:10397/24376. ISSN 0377-2217.
25. Gopalan, Parikshit; Klivans, Adam; Meka, Raghu; Štefankovic, Daniel; Vempala, Santosh; Vigoda, Eric (2011-10-01). "An FPTAS for #Knapsack and Related Counting Problems". 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. pp. 817–826. doi:10.1109/FOCS.2011.32. ISBN 978-0-7695-4571-4. S2CID 5691574.
26. Ergun, Funda; Sinha, Rakesh; Zhang, Lisa (2002-09-15). "An improved FPTAS for Restricted Shortest Path". Information Processing Letters. 83 (5): 287–291. doi:10.1016/S0020-0190(02)00205-3. ISSN 0020-0190.
27. Tsaggouris, George; Zaroliagis, Christos (2009-06-01). "Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-Linear Objectives with Applications". Theory of Computing Systems. 45 (1): 162–186. doi:10.1007/s00224-007-9096-4. ISSN 1433-0490. S2CID 13010023.
28. Lin, Chengyu; Liu, Jingcheng; Lu, Pinyan (2013-12-18), "A Simple FPTAS for Counting Edge Covers", Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, Society for Industrial and Applied Mathematics, pp. 341–348, arXiv:1309.6115, doi:10.1137/1.9781611973402.25, ISBN 978-1-61197-338-9, S2CID 14598468, retrieved 2021-12-13
29. Kel’manov, A. V.; Romanchenko, S. M. (2014-07-01). "An FPTAS for a vector subset search problem". Journal of Applied and Industrial Mathematics. 8 (3): 329–336. doi:10.1134/S1990478914030041. ISSN 1990-4797. S2CID 96437935.
30. Doerr, Benjamin; Eremeev, Anton; Neumann, Frank; Theile, Madeleine; Thyssen, Christian (2011-10-07). "Evolutionary algorithms and dynamic programming". Theoretical Computer Science. 412 (43): 6020–6035. arXiv:1301.4096. doi:10.1016/j.tcs.2011.07.024. ISSN 0304-3975.

External links

• Complexity Zoo: FPTAS