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.

[Top]

REVIEWS
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.

[Top]