English
资源说明：Most natural optimization problems, including those arising in important
application areas, are NP-hard. Therefore, under the widely believed conjecture
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 approximation
algorithms as it stands today. It is reasonable to expect the
picture to change with time.
This book is divided into three parts. In Part I we cover combinatorial
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 categorizing
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 primaldual
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 theorem
in mathematics (readers familiar with complexity theory will recognize
this as the philosophical point behind the P -=/= NP question).
本源码包内暂不包含可直接显示的源代码文件，请下载源码包。
