FREE Delivery in the UK.
Only 3 left in stock (more on the way).
Dispatched from and sold by Amazon. Gift-wrap available.
Quantity:1
Combinatorial Optimizatio... has been added to your Basket
FREE Delivery on orders over £10.
Condition: Used: Good
Comment: See item-Condition. Fulfillment by amazon.uk
Have one to sell?
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 – 1 Feb 2000

3.8 out of 5 stars 4 customer reviews

See all formats and editions Hide other formats and editions
Amazon Price
New from Used from
Kindle Edition
"Please retry"
Paperback
"Please retry"
£13.99
£6.08 £7.85
Note: This item is eligible for click and collect. Details
Pick up your parcel at a time and place that suits you.
  • Choose from over 13,000 locations across the UK
  • Prime members get unlimited deliveries at no additional cost
How to order to an Amazon Pickup Location?
  1. Find your preferred location and add it to your address book
  2. Dispatch to this address when you check out
Learn more
£13.99 FREE Delivery in the UK. Only 3 left in stock (more on the way). Dispatched from and sold by Amazon. Gift-wrap available.
click to open popover

Special Offers and Product Promotions


Frequently Bought Together

  • Combinatorial Optimization: Algorithms and Complexity (Dover Books on Computer Science)
  • +
  • Introduction to Graph Theory (Dover Books on Mathematics)
Total price: £23.98
Buy the selected items together

Enter your mobile number below and we'll send you a link to download the free Kindle App. Then you can start reading Kindle books on your smartphone, tablet, or computer - no Kindle device required.
Getting the download link through email is temporarily not available. Please check back later.

  • Apple
  • Android
  • Windows Phone

To get the free app, enter your mobile phone number.




Product details

  • Paperback: 528 pages
  • Publisher: Dover Publications Inc.; New edition edition (1 Feb. 2000)
  • Language: English
  • ISBN-10: 0486402584
  • ISBN-13: 978-0486402581
  • Product Dimensions: 3.2 x 14 x 21.6 cm
  • Average Customer Review: 3.8 out of 5 stars  See all reviews (4 customer reviews)
  • Amazon Bestsellers Rank: 99,249 in Books (See Top 100 in Books)

Product Description

About the Author

Christos H. Papadimitriou is C. Lester Hogan Professor of Electrical Engineering and Computer Sciences at the University of California, Berkeley, where he has taught since 1996 and where he is a former Miller Fellow.


Customer Reviews

3.8 out of 5 stars
Share your thoughts with other customers

Top Customer Reviews

Format: Paperback Verified Purchase
I bought this book for uni and it is generally quite good although very complex and in depth. I found it quite hard to read over all and there is a lot of complicated maths involved, buy as I said it was quite helpful for the course.
Comment One person found this helpful. Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback.
Sorry, we failed to record your vote. Please try again
Report abuse
By A Customer on 19 Jun. 1998
Format: Paperback
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.
Comment 9 people found this helpful. Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback.
Sorry, we failed to record your vote. Please try again
Report abuse
Format: Paperback
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.
2 Comments 6 people found this helpful. Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback.
Sorry, we failed to record your vote. Please try again
Report abuse
Format: Paperback
I'm only in the second chapter, but so far I have found this book very unpleasant to read. The book claims to be written for "mathematically sophisticated" students, but the definitions and proofs are often carelessly written regarding mathematical correctness. In every definition you have to guess what they mean with the undefined variables, and there is little further explanation if you didn't get it. It is not a very difficult subject, but the way it is presented here makes it impossible to grasp.
Comment One person found this helpful. Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback.
Sorry, we failed to record your vote. Please try again
Report abuse

Most Helpful Customer Reviews on Amazon.com (beta)

Amazon.com: HASH(0x92fc3018) out of 5 stars 25 reviews
77 of 79 people found the following review helpful
HASH(0x92d17e1c) out of 5 stars Inexpensive, excellently written, and quite interesting! 14 Nov. 2002
By Todd Ebert - Published on Amazon.com
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.
41 of 44 people found the following review helpful
By SeanFurl - Published on Amazon.com
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.
24 of 25 people found the following review helpful
HASH(0x93c46c54) out of 5 stars A Masterpiece on Combinatorial Optimisation 30 Nov. 1999
By KARTIK KRISHNAN S. - Published on Amazon.com
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).
19 of 19 people found the following review helpful
HASH(0x92d173c0) out of 5 stars It worths exponentially much more than its price 21 Jun. 2002
By G. Avvinti - Published on Amazon.com
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.
15 of 17 people found the following review helpful
HASH(0x93d54dc8) out of 5 stars Mmm, algorithms.... 11 Nov. 2006
By A. Cottrell - Published on Amazon.com
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.3 The Question of Finiteness of the Labeling Algorithm; 6.4 Dijkstra's Algorithm; 6.5 The Floyd-Warshall Algorithm

Chap. 7 Primal-Dual Algorithms for Min-Cost Flow 7.1 The Min-Cost Flow Problem; 7.2 Combinatorializing the Capacities--Algorithm Cycle; 7.3 Combinatorializing the Cost--Algorithm Buildup; 7.4 An Explicit Primal-Dual Algorithm for the Hitchcock Problem--Algorithm Alphabeta; 7.5 A Transformation of Min-Cost Flow to Hitchcock; 7.6 Conclusion

Chap. 8 Algorithms and Complexity 8.1 Computability; 8.2 Time Bounds; 8.3 The Size of an Instance; 8.4 Analysis of Algorithms; 8.5 Polynomial-Time Algorithms; 8.6 Simplex Is Not a Polynomial-Time Algorithm; 8.7 The Ellipsoid Algorithm; 8.7.1 LP, LI, and LSI; 8.7.2 Affine Transformations and Ellipsoids; 8.7.3 The Algorithm; 8.7.4 Arithmetic Precision

Chap. 9 Efficient Algorithms for the Max-Flow Problem 9.1 Graph Search; 9.2 What Is Wrong With the Labeling Algorithm; 9.3 Network Labeling and Digraph Search; 9.4 An O(|V|²) Max-Flow Algorithm; 9.5 The Case of Unit Capacities

Chap. 10 Algorithms For Matching 10.1 The Matching Problem; 10.2 A Bipartite Matching Algorithm; 10.3 Bipartite Matching and Network Flow; 10.4 Nonbipartite Matching: Blossoms; 10.5 Nonbipartite Matching: An Algorithm

Chap. 11 Weighted Matching 11.1 Introduction; 11.2 The Hungarian Method for the Assignment Problem; 11.3 The Nonbipartite Weighted Matching Problem; 11.4 Conclusions

Chap. 12 Spanning Trees and Matroids 12.1 The Minimum Spanning Tree Problem; 12.2 An O(|E|log|V|) Algorithm for the Minimum Spanning Tree Problem; 12.3 The Greedy Algorithm; 12.4 Matroids; 12.5 The Intersection of Two Matroids; 12.6 On Certain Extensions of the Matroid Intersection Problem; 12.6.1 Weighted Matroid Intersection; 12.6.2 Matroid Parity; 12.6.3 The Intersection of Three Matroids

Chap. 13 Interger Linear Programming 13.1 Introduction; 13.2 Total Unimodularity; 13.3 Upper Bounds for Solutions of ILPs

Chap. 14 A Cutting-Plane Algorithm for Integer Linear Programs 14.1 Gomory Cuts; 14.2 Lexicography; 14.3 Finiteness of the Fractional Dual Algorithm; 14.4 Other Cutting-Plane Algorithms

Chap. 15 NP-Complete Problems 15.1 Introduction; 15.2 An Optimization Problem Is Three Problems; 15.3 The Classes P and NP; 15.4 Polynomial-Time Reductions; 15.5 Cook's Theorem; 15.6 Some Other NP-Complete Problems: Clique and the TSP; 15.7 More NP-Complete Problems: Matching, Covering, and Partitioning

Chap. 16 More About NP-Completeness 16.1 The Class co-NP; 16.2 Pseudo-Polynomial Algorithms and "Strong" NP-Complete Problems; 16.3 Special Cases and Generalizations of NP-Complete Problems; 16.3.1 NP-Completeness By Restriction; 16.3.2 Easy Special Cases of NP-Complete Problems; 16.3.3 Hard Special Cases of NP-Complete Problems; 16.4 A Glossary of Related Concepts; 16.4.1 Polynomial-Time Reductions; 16.4.2 NP-Hard problems; 16.4.3 Nondeterministic Turing Machines; 16.4.4 Polynomial-Space Complete Problems; 16.5 Epilogue

Chap. 17 Approximation Algorithms 17.1 Heuristics for Node Cover: An Example; 17.2 Approximation Algorithm for the Traveling Salesman Problem; 17.3 Approximation Schemes; 17.4 Negative Results

Chap. 18 Branch-and-Bound and Dynamic Programming 18.1 Branch-and-Bound for Integer Linear Programming; 18.2 Branch-and-Bound in a General Context; 18.3 Dominance Relations; 18.4 Branch-and-Bound Strategies; 18.5 Application to a Flowshop Scheduling Problem; 18.6 Dynamic Programming

Chap. 19 Local Search 19.1 Introduction; 19.2 Problem 1: The TSP; 19.3 Problem 2: Minimum-Cost Survivable Networks; 19.4 Problem 3: Topology of Offshore Natural Gas Pipeline Systems; 19.5 Problem 4: Uniform Graph Partitioning; 19.6 General Issues in Local Search; 19.7 The Geometry of Local Search; 19.8 An Example of a Large Minimal Exact Neighborhood; 19.9 The Complexity of Exact Local Search for the TSP

All chapters have problem sets and notes and references.

As can be seen, this book has a mighty amount of information, and it is amazingly well-explained. Of course, you need a firm grasp of your linear algebra, and some knowledge of very elementary calc./real analysis and graph theory (although most of the graph theory needed, technically speaking, is supplied in an appendix). You don't even really need to know a programming language, since the authors use a "pidgin algol," explained in yet another appendix, for most of the algorithm stuff; all it takes is an orderly thought process to follow it.

Despite the book's age, it mostly holds up very well in terms of topics and presentation. In the preface to the Dover edition, the authors briefly discuss some more current topics not dealt with in the text and make some (probably also out of date!) referrals for those wishing to "catch up." All in all, this book is a great value both as a text and a reference.
Were these reviews helpful? Let us know


Feedback