O'Reilly logo

A Guide to Algorithm Design by Frédéric Vivien, Yves Robert, Anne Benoit

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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 first 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 efficiently encoding real numbers). The difficulty 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 briefly 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 first define 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 defined 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 find 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 difference between PTAS and FPTAS is simply that the ε quantifier
changes sides. For a PTAS, ε is a fixed 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 define asymptotic PTAS and FPTAS, which add a constant to
the approximation scheme. We define formally only the APTAS for a mini-
mization problem, and the definition 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.

Start Free Trial

No credit card required