Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties
This book documents the state of the art in combinatorial optimization, presenting approximate solutions of virtually all relevant classes of NP-hard optimization problems. The wealth of problems, algorithms, results, and techniques make it an indispensible source of reference for professionals. The text smoothly integrates numerous illustrations, examples, and exercises.
Hardcover, 543 pages
Published February 1st 2003 by Springer
To see what your friends thought of this book, please sign up.
(showing 1-12 of 12)
The current state of knowledge of approximation algorithms. As every undergraduate CS major learns (and high schoolers can be taught to understand), NP-complete problems most likely have no polynomial algorithms to solve them. In the 30 years since this question was first posed (actually, it was first posed in a letter Gödel wrote to von Neumann in 1954, but neither great man publicized it) no one has been able to prove it, or prove that it is impossible to prove it, and no one has been able to...more