Combinatorial Optimization: Algorithms and Complexity (Dover Books on Computer Science) by Christos H. Papadimitriou (PDF)

Description

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.

User’s Reviews

Reviews from Amazon users which were colected at the time this book was published on the website:

⭐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 ProblemsChap. 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 PivotingChap. 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 AlgorithmChap. 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 DecompositionChap. 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-FlowChap. 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 AlgorithmChap. 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 ConclusionChap. 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 PrecisionChap. 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 CapacitiesChap. 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 AlgorithmChap. 11 Weighted Matching 11.1 Introduction; 11.2 The Hungarian Method for the Assignment Problem; 11.3 The Nonbipartite Weighted Matching Problem; 11.4 ConclusionsChap. 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 MatroidsChap. 13 Interger Linear Programming 13.1 Introduction; 13.2 Total Unimodularity; 13.3 Upper Bounds for Solutions of ILPsChap. 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 AlgorithmsChap. 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 PartitioningChap. 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 EpilogueChap. 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 ResultsChap. 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 ProgrammingChap. 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 TSPAll 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.

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

⭐This is an excellent reference on the subject. The book methodically presents proofs for everything. It’s a bit dense though and it might be a good idea to accompany this with something more introductory on some of its topics (graphs problems, linear programming etc), such as Cormen’s book on algorithms.

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

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

⭐Wonderful text on combinatorial optimization. The treatment of linear optimization alone is worth the price of admission. I like the unifying point of view of various combinatorial algorithms in a primal-dual framework. Unifying frameworks are always insightful to add to your arsenal of insights.

⭐Content-wise, the book is timeless and I find it pleasant to read despite being a non-expert in the field. However, the edition is so low-quality that it would be unworthy of even the poorest of college publishers. Some pages are not even properly separated at the top and the paper has been cut in a rough way (see picture). Maybe it is an issue with my copy only, but such a book would deserve more respect.

⭐Eine Warnung vorweg: dies ist mein bisher erstes Buch zum Thema. Daher kann ich es nicht mit anderen Büchern zur selben Thematik vergleichen. Quasi sind die fünf Sterne “absolut” und nicht “relativ” zu verstehen.Das Buch ist in leicht verständlichem Englisch geschrieben. Die Kapitel zu NP Complete, Branch & Bound fand ich besonders schön. Zu jeder Definition sind auch für den Nicht-Mathematiker verständliche Beispiele angegeben. Obwohl mir das Buch für meine spezielle Problemstellung nicht direkt geholfen hat und Local Search Verfahren und Heurismen etwas zu kurz kommen, war es doch gut um die Grundlagen zu legen und ist auch als Nachschlagewerk geeignet. Didaktisch sehr schön aufgebaut. Beweise werden an Stellen geführt, wo sie der Intuition dienen, nicht nur des Beweises wegen. Ich hätte mir noch Lösungen für die Übungsaufgaben gewünscht. Wahrscheinlich nicht auf dem neusten Stand (kann ich nicht beurteilen) und wie gesagt sind für viele “real world” Probleme keine echten Lösungsansätze angeboten, aber dafür gibts ja auch noch wissenschaftliche paper. Als Einführung und Grundlagenwerkfand find ich es klasse.Fazit: Ein Buch über Combinatorial Optimization, mit schönem Schriftbild, schönen Abbildungen und einer MENGE Inhalt….für nich mal 14EUR! Das sollte sich der Springer-Verlag mal hinter die Ohren schreiben:)Jutes DingLo avevo usato venticinque anni fa per preparare un esame. Il libro è datato, la stesura originale è del 1982, tuttavia contiene nozioni fondamentali, ben sviluppate, sull’ottimizzazione combinatoria, trattate con sufficiente rigore formale.Lo consiglierei come testo di base, per gli approfondimenti pratici esistono testi specifici deciamente più settoriali.Il prezzo è davvero stracciato, varrebbe la pena anche se fosse utile un solo capitolo.

⭐

Keywords

Free Download Combinatorial Optimization: Algorithms and Complexity (Dover Books on Computer Science) in PDF format
Combinatorial Optimization: Algorithms and Complexity (Dover Books on Computer Science) PDF Free Download
Download Combinatorial Optimization: Algorithms and Complexity (Dover Books on Computer Science) 1998 PDF Free
Combinatorial Optimization: Algorithms and Complexity (Dover Books on Computer Science) 1998 PDF Free Download
Download Combinatorial Optimization: Algorithms and Complexity (Dover Books on Computer Science) PDF
Free Download Ebook Combinatorial Optimization: Algorithms and Complexity (Dover Books on Computer Science)