Approximation Algorithms [Vazirani 2004-03-22].pdf

(1435 KB) Pobierz
Vijay V. Vazirani
College of Computing
Georgia Institute of Technology
Copyright c 2001
Approximation Algorithms
Springer
Berlin Heidelberg NewYork
Barcelona Hong Kong
London Milan Paris
Singapore Tokyo
To my parents
Preface
Although this may seem a paradox, all exact
science is dominated by the idea of approximation.
Bertrand Russell (1872–1970)
Most natural optimization problems, including those arising in important
application areas, are
NP-hard.
Therefore, under the widely believed con-
jecture that
P
=
NP,
their exact solution is prohibitively time consuming.
Charting the landscape of approximability of these problems, via polynomial
time algorithms, therefore becomes a compelling subject of scientific inquiry
in computer science and mathematics. This book presents the theory of ap-
proximation algorithms as it stands today. It is reasonable to expect the
picture to change with time.
The book is divided into three parts. In Part I we cover a combinato-
rial algorithms for a number of important problems, using a wide variety
of algorithm design techniques. The latter may give Part I a non-cohesive
appearance. However, this is to be expected – nature is very rich, and we
cannot expect a few tricks to help solve the diverse collection of
NP-hard
problems. Indeed, in this part, we have purposely refrained from tightly cat-
egorizing algorithmic techniques so as not to trivialize matters. Instead, we
have attempted to capture, as accurately as possible, the individual character
of each problem, and point out connections between problems and algorithms
for solving them.
In Part II, we present linear programming based algorithms. These are
categorized under two fundamental techniques: rounding and the primal–
dual schema. But once again, the exact approximation guarantee obtainable
depends on the specific LP-relaxation used, and there is no fixed recipe for
discovering good relaxations, just as there is no fixed recipe for proving a the-
orem in mathematics (readers familiar with complexity theory will recognize
this as the philosophical point behind the
P
=
NP
question).
Part III covers four important topics. The first is the problem of finding
a shortest vector in a lattice which, for several reasons, deserves individual
treatment (see Chapter 27).
The second topic is the approximability of counting, as opposed to
optimization, problems (counting the number of solutions to a given in-
stance). The counting versions of all known
NP-complete
problems are #P-
complete
1
. Interestingly enough, other than a handful of exceptions, this is
true of problems in
P
as well. An impressive theory has been built for ob-
1
However, there is no theorem to this effect yet.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin