Combinatorial Optimization: Algorithms and Complexity

After reading this and Papadimitriou's "Introduction to Computational Complexity" (which I also highly recommend), I now consider him one of the best at conveying complex ideas in a way that rarely confuses the reader. I also had the priviledge of attending one of his talks on complexity, and he seems just as effusive and transparent as a lecturer as he does a writer. Ah, for once I bought a Dover book that did not disappoint.


A Masterpiece on Combinatorial Optimisation   November 30, 1999
KARTIK KRISHNAN S. (Hamilton, Ontario Canada)
19 out of 20 found this review helpful

Christos Papadimitriou, my hero is a hope for all of us who wish to master the fascinating field of Combinatorial Optimisation. Especially recommended are the chapters on matching, NP Completeness and Approximation Algorithms.

As another reader has remarked, this book is quite old though (published first in 1982). For a more to date book on Combinatorial Optimisation, one might want to look at Cook, Cunningham, Pulleyblank and Schrijver's book on Combinatorial Optimisation (published in 1998).


It worths exponentially much more than its price   June 21, 2002
G. Avvinti (Sicily, Italy)
12 out of 12 found this review helpful

One could buy this book for different reasons: interests in combinatorial optimization, of course; interests in what Papadimitriou has to say, since his thoughts on this subject are definitely invaluable; perhaps the price is a good reason alone.
Whatever the reason, however, I think that would be a rare event to remain duped.

I was preparing my exam in Computability and Complexity when I first used it. I've been wonderfully surprised by the amount of definitions, algorithms, concepts I've found in this book. I think one could use this book for a simple course on Algorithms, on Computability and/or Complexity, on the whole Combinatorial Optimization, and the book would be always and costantly useful.

The chapters on algorithms and complexity, or those on NP completeness have proved to be gems. The chapters on Approximation and Local Search are great, and they feature a bunch of detailed and excellent quality stuff (e.g. there is a detailed treatment of Christofides' algorithm to approximate the TSP, that is quite an idiosyncratic topic).

All in all, a very great book, with a value exponentially greater than the very insignificant price.


A great book and a great deal   November 17, 2001
JAMIE R LAWSON (San Diego, CA United States)
5 out of 5 found this review helpful

As a computer science graduate student I carried Papadimitriou and Steiglitz with me almost every day. Its target subject is combinatorial optimization, but going through this book, you might think that graph theory and computational complexity are just subfields of combinatorial optimization. It builds a beautiful theory that brings these and other fields together, and with a fraction of the page count of, say, Cormen, Rivest Leiserson. Now that it's a Dover book, it's a fraction of the price I paid, and I was gladly willing to pay that.


a great bargain   April 17, 2006
J. Ye (Boston, MA)
3 out of 3 found this review helpful

It is my favorite book on combinatorial optimization. The last 5 chapters 15-19 are the most interesting and useful to me because my job is write heuristics for NP hard problems in transportation. Chatpers 15 and 16 on NP complete problems are well explained and covered in depth. Chapter 17 on approximation algorithms is easy to understand and fun to read. Chapters 18 (branch-and-bound and dynamic programming) and 19 (local search) are very practical stuff, which I read many times.

The rest of the book is a good reference for topics like linear programming, max-flow, matching, etc. There are mostly independent of the last 5 chapters and can be skipped on a first read. My experience is that I don't need detailed knowledge of simplex algorithms because I use CPlex.