You are here

Combinatorial Optimization: Algorithms and Complexity

Christos H. Papadimitriou and Kenneth Steiglitz
Dover Publications
Publication Date: 
Number of Pages: 
[Reviewed by
Brian Borchers
, on

This is a Dover reprint of a classic textbook originally published in 1982. The book is about combinatorial optimization problems, their computational complexity, and algorithms for their solution. It begins with eight chapters on the simplex method for linear programming and network flow problems. The ellipsoid algorithm is introduced as a polynomial time algorithm for linear programming in chapter 8.

The remaining chapters of the book discuss polynomial time algorithms for various combinatorial optimization problems, NP-Completeness, and approaches to dealing with NP-Complete problems including integer linear programming, meta heuristics, and approximation algorithms.

At the time of its original publication, this book provided a broad overview of the entire field of combinatorial optimization and introduced many significant new areas of research. Although the book is still very readable as an introduction to combinatorial optimization and NP-Completeness, it can no longer be recommended as an up-to-date source on these subjects. A more up to date textbook that covers many of the same topics is Combinatorial Optmiziation: Theory and Algorithms, by Bernhard Vygen and Jens Korte.

Brian Borchers is a professor of Mathematics at the New Mexico Institute of Mining and Technology. His interests are in optimization and applications of optimization in parameter estimation and inverse problems.

The table of contents is not available.