## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

Chapter 8
Beyond NP-completeness
At the conclusion of Chapter 6, we stated that proving a problem is NP-
complete does not make it go away. The subject of this chapt er is to go
beyond NP-completeness and to describe the various approaches that can be
taken when confronted with an NP-complete problem.
The ﬁrst approach (see Section 8.1) is the most elegant. When deriving
approximation algorithms, we search for an approximate solution, but we also
guarantee that it is of good quality. Of course, the approximated solution
must be found in polynomial time.
The second approach (see Section 8.2) is less ambitious. Given an NP-
complete problem, we show how to characterize particular instances that have
polynomial complexity.
The third approach (see Section 8.3) often provides useful lower bounds.
The idea is to cast the optimization problem under study in terms of a lin-
ear program. While solving a linear program with integer variables is NP-
complete, solving a linear program with rational variables has polynomial
complexity (we are restricted to rational variables because of the impossibil-
ity of eﬃciently encoding real numbers). The diﬃculty is then to reconstruct
a solution of the integer linear program from an optimal solution of that pro-
gram with rational variables. This is not always possible, but this method at
least provides a lower bound on any optimal integer solution.
We brieﬂy introduce, in Section 8.4, randomized algorithms as a fourth ap-
proach that solves “most” instances of an NP-complete problem in polynomial
time.
Finally, we pr ovide in Section 8.5 a detailed discussion of branch-and-bound
and backtracking strategies, where one explores the space of all potential so-
lutions in a clever way. While the worst-case exploration may require expo-
nential time, on average, the optimal solution is found in “reasonable” time.
8.1 Approximation results
In this section, we ﬁrst deﬁne polynomial-time approximation algorithms and
(fully) polynomial-time approximation schemes (PTAS and FPTAS). Then,
179
© 2014 by Taylor & Francis Group, LLC
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
time.
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
1
ε
is a constant as
well. On the contrary, the complexity of an FPTAS scheme must be polyno-
mial in
1
ε
. 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

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required