Programming Books C Java PHP Python Learn more Browse Programming Books
Combinatorial Optimization: Algorithms and Complexity and over one million other books are available for Amazon Kindle. Learn more
Buy New
$13.97
Qty:1
  • List Price: $21.95
  • Save: $7.98 (36%)
FREE Shipping on orders over $35.
In Stock.
Ships from and sold by Amazon.com.
Gift-wrap available.
Combinatorial Optimizatio... has been added to your Cart
Have one to sell? Sell on Amazon
Flip to back Flip to front
Listen Playing... Paused   You're listening to a sample of the Audible audio edition.
Learn more
See all 2 images

Combinatorial Optimization: Algorithms and Complexity (Dover Books on Computer Science) Paperback – Unabridged, January 29, 1998

ISBN-13: 978-0486402581 ISBN-10: 0486402584 Edition: Unabridged

Buy New
Price: $13.97
51 New from $11.99 36 Used from $6.25
Amazon Price New from Used from
eTextbook
"Please retry"
Paperback, Unabridged
"Please retry"
$13.97
$11.99 $6.25
Free%20Two-Day%20Shipping%20for%20College%20Students%20with%20Amazon%20Student


Frequently Bought Together

Combinatorial Optimization: Algorithms and Complexity (Dover Books on Computer Science) + Introduction to Graph Theory (Dover Books on Mathematics) + An Introduction to Information Theory: Symbols, Signals and Noise (Dover Books on Mathematics)
Price for all three: $21.95

Buy the selected items together

NO_CONTENT_IN_FEATURE

Best Books of the Month
Best Books of the Month
Want to know our Editors' picks for the best books of the month? Browse Best Books of the Month, featuring our favorite new books in more than a dozen categories.

Product Details

  • Series: Dover Books on Computer Science
  • Paperback: 528 pages
  • Publisher: Dover Publications; Unabridged edition (January 29, 1998)
  • Language: English
  • ISBN-10: 0486402584
  • ISBN-13: 978-0486402581
  • Product Dimensions: 8.5 x 5.5 x 1 inches
  • Shipping Weight: 1.2 pounds (View shipping rates and policies)
  • Average Customer Review: 4.6 out of 5 stars  See all reviews (19 customer reviews)
  • Amazon Best Sellers Rank: #244,954 in Books (See Top 100 in Books)

More About the Author

Christos Papadimitriou was born and raised in Athens, Greece, and studied in Athens and at Princeton. He has taught Computer Science at Harvard, MIT, Stanford, and, since 1996, at Berkeley, where he is the C. Lester Hogan Professor of Computer Science. In his research he uses mathematics to understand the power and limitations of computers. He is a member of the National Academy of Sciences, the American Academy of Arts and Sciences, and the National Academy of Engineering. He has written several of the standard textbooks in algorithms and computation, and two novels: "Turing" and "Logicomix" (with Apostolos Doxiadis, art by Alecos Papadatos and Annie di Donna). He is working on his third novel, "Independence."


Customer Reviews

4.6 out of 5 stars
5 star
15
4 star
2
3 star
1
2 star
1
1 star
0
See all 19 customer reviews
On another, it serves as a good reference for many graph-theoretic algorithms.
Todd Ebert
Chapters 18 (branch-and-bound and dynamic programming) and 19 (local search) are very practical stuff, which I read many times.
J. Ye
Despite the book's age, it mostly holds up very well in terms of topics and presentation.
A. Cottrell

Most Helpful Customer Reviews

64 of 66 people found the following review helpful By Todd Ebert on November 14, 2002
Format: Paperback Verified Purchase
I had this book on my shelf for two years before taking a serious look at it, and only wish I had read it much earlier in life. Christos Papadimitriou has written quite a gem! On one hand this book serves as a good introduction to combinatorial optimization algorithms, in that it provides a flawless introduction to the simplex algorithm, linear and integer programming, and search techniques such as Branch-and-Bound and dynamic programming. On another, it serves as a good reference for many graph-theoretic algorithms. But most importantly Papadimitriou and Steiglitz seem to be on a quest to understand why some problems, such as Minimum Path or Matching, have efficient solutions, while others, such as Traveling Salesman, do not. And in doing so they end up providing the reader with a big picture behind algorithms and complexity, and the connection between optimization problems 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.
2 Comments Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again
37 of 38 people found the following review helpful By SeanFurl on May 7, 1999
Format: Paperback
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. Most programmers don't need combinatorial optimization and for those who do there are some good alternative books.
2 Comments Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again
23 of 24 people found the following review helpful By KARTIK KRISHNAN S. on November 30, 1999
Format: Paperback
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).
Comment Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again
16 of 16 people found the following review helpful By G. Avvinti on June 21, 2002
Format: Paperback Verified Purchase
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.
Comment Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again
8 of 9 people found the following review helpful By A. Cottrell on November 11, 2006
Format: Paperback Verified Purchase
This is a very nice, self-contained introduction to linear programming, algorithm design and analysis, and computational complexity. The contents are as follows:

Chap. 1 Optimization Problems 1.1 Introduction; 1.2 Optimization Problems; 1.3 Neighborhoods; 1.4 Local and Global Optima; 1.5 Convex Sets and Functions; 1.6 Convex Programming Problems

Chap. 2 The Simplex Algorithm 2.1 Forms of the Linear Programming Problem; 2.2 Basic Feasible Solutions; 2.3 The Geometry of Linear Programs; 2.3.1 Linear and Affine Spaces; 2.3.2 Convex Polytopes; 2.3.3 Polytopes and LP; 2.4 Moving from bfs to bfs; 2.5 Organization of a Tableau; 2.6 Choosing a Profitable Column; 2.7 Degeneracy and Bland's Anticycling Algorithm; 2.8 Beginning the Simplex Algorithm; 2.9 Geometric Aspects of Pivoting

Chap. 3 Duality 3.1 The Dual of a Linear Program in General Form; 3.2 Complementary Slackness; 3.3 Farkas' Lemma; 3.4 The Shortest-Path Problem and Its Dual; 3.5 Dual Information in the Tableau; 3.6 The Dual Simplex Algorithm; 3.7 Interpretation of the Dual Simplex Algorithm

Chap. 4 Computational Considerations for the Simplex Algorithm 4.1 The Revised Simplex Algorithm; 4.2 Compuational Implications of the Revised Simplex Algorithm; 4.3 The Max-Flow Problem and Its Solution by the Revised Method; 4.4 Dantzig-Wolfe Decomposition

Chap. 5 The Primal-Dual Algorithm 5.1 Introduction; 5.2 The Primal-Dual Algorithm; 5.3 Comments on the Primal-Dual Algorithm; 5.4 The Primal-Dual Method Applied to the Shortest-Path Problem; 5.5 Comments on Methodology; 5.6 The Primal-Dual Method Applied to Max-Flow

Chap. 6 Primal-Dual Algorithms for Max-Flow and Shortest Path: Ford-Fulkerson and Dijkstra 6.1 The Max-Flow, Min-Cut Theorem; 6.2 The Ford and Fulkerson Labeling Algorithm; 6.
Read more ›
Comment Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again

Most Recent Customer Reviews