Papadimitriou, Christos H.     Combinatorial optimization : algorithms and complexity / Christos H. Papadimitriou, Kenneth Steiglitz. - Mineola, N.Y. : Dover Publications, Inc., 1998. - Corrected, unabridged republication. -  xvi, 496 p. : ill. ; 22 cm. - Includes bibliographical references and index. ISBN 0-486-40258-4 (pbk.)    : 204.80 KV99/3878 mathematical optimization combinatorial optimization computational complexity

From The Publisher:
This book brings together in one volume the important ideas of computational complexity developed by computer scientists with the foundations of mathematical programming developed by the operations research community.
The first seven chapters comprise a self-contained treatment of linear programming and duality theory, with an emphasis on graph and network flow interpretations. Chapter 8 is a transition chapter which introduces the techniques for analyzing the complexity of algorithms. Modern, fast algorithms for flow,  matching, and spanning trees, as well as the general setting of matroids, are described in Chapters 9--12. The remaining chapters(13--19) treat integer linear programming, including Gomory's cutting-plane algorithm, new ideas of the theory of NP-completeness and its ramifications, and practical ways of dealing with intractable problems--approximation algorithms, branch-and-bound, dyanmic programming, and local (or neighborhood) search.

Booknews, Inc.
 A text for a range of graduate courses, with some of the material suitable for students of computer science with a background in the theory of algorithms and some suitable for those with a background in operations research. Corrected and unabridged from the 1982 publication by Prentice-Hall, with a new
preface.

Customer Comments
Average Customer Review:  Number of Reviews: 2

sean@struct.net from San Francisco, CA , May 7, 1999
A classic. This is just a note to mention that athough Amazon has dated this book as  published in 1998, it is actually around 15 years old. By the way, it's a good  book, but I didn't find it an easy read, especially the first half. One needs to already have a foundation in linear programming and optimization to digest it. A
previous reviewer who said that every programmer should read it was being unduly exuberant, presumably because it happened to hit his particular spot. There are some good alternative books.

jd.bertron@cgm.com from Boulder, Colorado , June 19, 1998

Excellent. Every programmer should have read this book. It is complete, detailed and
makes a great reference for the engineer's bookshelf. It goes beyong the enumeration of cookie-cutter algorithms , by providing enough theory, to let  you create solutions to your own optimization problems.