180 Chapter 8. Beyond NP-completeness
we give some examples of approximation and inapproximability results.
8.1.1 Approximation algorithms
In Chapter 6, we have deﬁned the NP-completeness of problems and exhibited
several NP-complete decision problems. As discussed in Section 6.3.4, the
target problem is often an optimization problem that has been restricted to a
decision problem so that we can prove its NP-completeness.
If the optimal solution of an optimization problem cannot be found in poly-
nomial time, one may want to ﬁnd an approximate solution in polynomial
DEFINITION 8.1. A λ-approximation algorithm is an algorithm whose
execution time is polynomial in the instance size and that returns an approx-
imate solution guaranteed to be, in the worst case, at a factor λ away from
the optimal solution.
For instance, for each instance I of a minimization pr oblem, the solution
of the approximation algorithm f or instan ce I must be smaller than or equal
to λ times the optimal solution for instance I.
The closer λ to 1, the better the approximation algorithm. We catego-
rize some particular approximation algorithms for which λ is close to 1 as
polynomial-time approximation schemes.
DEFINITION 8.2. A Polynomial-Time Approximation Scheme (PTAS) is
such that for any constant λ = 1 + ε > 1, there exists a λ-approximation algo-
rithm, i.e., an algorithm that is polynomial in t he instance size and guaranteed
at a factor λ.
Note that the algorithm may not be polynomial in 1/ε and thus have a
high complexity when ε gets close to zero. A Fully PTAS is such that the
algorithm is polynomial both in the instance size and in 1/ε.
DEFINITION 8.3. A Fully Polynomial-Time Approximation Scheme, or
FPTAS, is such that for any constant λ = 1 + ε > 1, there exists a λ-
approximation algori thm that is polynomial in the instance size and in 1/ε.
The diﬀerence between PTAS and FPTAS is simply that the ∀ε quantiﬁer
changes sides. For a PTAS, ε is a ﬁxed constant, so that 2
is a constant as
well. On the contrary, the complexity of an FPTAS scheme must be polyno-
. Of course, having an FPTAS is a stronger property than having
a PTAS (i.e., FPTAS ⇒ PTAS).
Finally, we deﬁne asymptotic PTAS and FPTAS, which add a constant to
the approximation scheme. We deﬁne formally only the APTAS for a mini-
mization problem, and the deﬁnition can easily be extended for maximization
problems and AFPTAS.
© 2014 by Taylor & Francis Group, LLC