What do you think?
Rate this book
Combinatorial Optimization: Algorithms and Complexity
This clearly written, mathematically rigorous text includes a novel algorithmic exposition of the simplex method and also discusses the Soviet ellipsoid algorithm for linear programming; efficient algorithms for network flow, matching, spanning trees, and matroids; the theory of NP-complete problems; approximation algorithms, local search heuristics for NP-complete problems, more. All chapters are supplemented by thought-provoking problems. A useful work for graduate-level students with backgrounds in computer science, operations research, and electrical engineering. "Mathematicians wishing a self-contained introduction need look no further." — American Mathematical Monthly.
528 pages, Paperback
First published March 15, 2012
47 people are currently reading
504 people want to read
About the author
Christos H. Papadimitriou
14 books37 followersChristos Harilaos Papadimitriou (Greek: Χρίστος Χ. Παπαδημητρίου) is a Professor in the Computer Science Division at the University of California, Berkeley, United States.
Papadimitriou is the author of the textbook Computational Complexity and has co-authored Algorithms with Sanjoy Dasgupta and Umesh Vazirani.
He has collaborated with Apostolos Doxiadis on the graphic novel Logicomix, and has published one novel, Turing.
Papadimitriou is the author of the textbook Computational Complexity and has co-authored Algorithms with Sanjoy Dasgupta and Umesh Vazirani.
He has collaborated with Apostolos Doxiadis on the graphic novel Logicomix, and has published one novel, Turing.
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 - 10 of 10 reviews
December 5, 2007
An immediate classic and still the basic textbook in its field, you simply will not find a better deal than this $19.95 gift to the combinatorially-minded public from the wonderful folk at Dover Mathematical Publishing ([sniff] god bless and keep those men!).
March 31, 2015
First: I'm no expert in optimization, and this might be one reason why I did not like this book that much. I also skipped a good portion of the book, which I considered not being relevant for my work. One of the main drawbacks of this book is that, although the title speaks of combinatorial optimization, the topic is (integer) linear programming. I would have preferred at least a few chapters on nonlinear integer problems.
Chapter 2 concerned the simplex algorithm and was a pleasure to read. Chapter 3 dealt with the dual of a program, a concept which still escapes my understanding. I skipped Chapters 4-7 which concern the primal-dual algorithm and implementations (nowadays, I think LPs are solved using computer software). After a brief introduction to Landau's notation and complexity in Chapter 8, there are again three chapters devoted only to algorithms. I would have preferred a more rigorous treatment of matroids in Chapter 12; the chapters on integer LPs and the cutting-plane algorithm were excellently written. Chapters 15 and 16 introduce NP-complete problems, and Chapter 17 suggests approximative algorithms. Very interesting is again Chapter 18, which is almost exclusively devoted to the branch-and-bound method. Chapter 19, on local search, is exemplary for the overall appearance of the book: It is so full of examples that the big picture does not come across.
Chapter 2 concerned the simplex algorithm and was a pleasure to read. Chapter 3 dealt with the dual of a program, a concept which still escapes my understanding. I skipped Chapters 4-7 which concern the primal-dual algorithm and implementations (nowadays, I think LPs are solved using computer software). After a brief introduction to Landau's notation and complexity in Chapter 8, there are again three chapters devoted only to algorithms. I would have preferred a more rigorous treatment of matroids in Chapter 12; the chapters on integer LPs and the cutting-plane algorithm were excellently written. Chapters 15 and 16 introduce NP-complete problems, and Chapter 17 suggests approximative algorithms. Very interesting is again Chapter 18, which is almost exclusively devoted to the branch-and-bound method. Chapter 19, on local search, is exemplary for the overall appearance of the book: It is so full of examples that the big picture does not come across.
April 19, 2021
Superb.
A deep and thorough coverage of combinatorial optimisation ( optimisation over discrete/finite spaces ). It’s not an easy read. You’ll have to slow right down and nut it all out for optimum benefit. Work though the proofs and the algorithms.
There is a strong focus on Linear Programming and Duality and a clear explanation of why it is as central to Combinatorial optimisation as it is to constrained optimisation over ‘continuous’ spaces.
I was especially intrigued by the material on local search. A powerful natural approach which often works well. But there is a detailed proof that it only works for the archetypal and NP Complete Travelling Salesman Problem if P = NP. And there is of course fat chance of that.
The book is an intellectual feast full of ideas and always grasping for deeper results in this fascinating and fundamental subject. A subject which will have profound theoretical and practical applications. Even more than it already does.
The book is also very practical. Giving detailed descriptions of algorithms and detailed proofs of their properties and interrelationships.
Like I said not an easy read though, so clear your schedule for at least a few days.
A deep and thorough coverage of combinatorial optimisation ( optimisation over discrete/finite spaces ). It’s not an easy read. You’ll have to slow right down and nut it all out for optimum benefit. Work though the proofs and the algorithms.
There is a strong focus on Linear Programming and Duality and a clear explanation of why it is as central to Combinatorial optimisation as it is to constrained optimisation over ‘continuous’ spaces.
I was especially intrigued by the material on local search. A powerful natural approach which often works well. But there is a detailed proof that it only works for the archetypal and NP Complete Travelling Salesman Problem if P = NP. And there is of course fat chance of that.
The book is an intellectual feast full of ideas and always grasping for deeper results in this fascinating and fundamental subject. A subject which will have profound theoretical and practical applications. Even more than it already does.
The book is also very practical. Giving detailed descriptions of algorithms and detailed proofs of their properties and interrelationships.
Like I said not an easy read though, so clear your schedule for at least a few days.
April 17, 2008
a $19 classic text on combinatorial optimization. thank you dover.
January 20, 2024
truly an amazing book. I really love this book. I only read up to the chapter on integer linear programming.
Clearest explanation of duality in linear programs and its applications i've ever seen.
Clearest explanation of duality in linear programs and its applications i've ever seen.
November 27, 2021
An amazing work of art, at a very reasonable price (thanks Dover!).
Papadimitriou & Steiglitz manage the impossible: in one book they introduce the reader to the most important mathematical problems of Operations Research (O.R.) and at the same time they introduce them to the theory of Computational Complexity. Pretty much for every problem that is being viewed from the lens of O.R., there is a corresponding analysis later where its computational complexity is being discussed, and by doing so the reader is being introduced to all the important aspects of the complexity theory: NP-completeness, approximation algorithms, branch and bound, local search. Really a must-read for anyone interested on discrete mathematical problems found in Operations Research, how computer scientists solve them, and what is this computational theory everyone is talking about?
Papadimitriou & Steiglitz manage the impossible: in one book they introduce the reader to the most important mathematical problems of Operations Research (O.R.) and at the same time they introduce them to the theory of Computational Complexity. Pretty much for every problem that is being viewed from the lens of O.R., there is a corresponding analysis later where its computational complexity is being discussed, and by doing so the reader is being introduced to all the important aspects of the complexity theory: NP-completeness, approximation algorithms, branch and bound, local search. Really a must-read for anyone interested on discrete mathematical problems found in Operations Research, how computer scientists solve them, and what is this computational theory everyone is talking about?
April 18, 2019
A bit shocked when I read KKT sufficiency criterion being applied to concave constrained NL problem...a bit rattled by this...I think this is a more computer science oriented book than a rigorous mathematical text
December 30, 2022
Very clear explanations.
Want to read
January 23, 2010another gem from Dover
Read
October 24, 2017about all of algorithm
This entire review has been hidden because of spoilers.
Displaying 1 - 10 of 10 reviews