|
Combinatorial Optimization: Algorithms and Complexity
by Christos H. Papadimitriou
Product Group: Book
Publisher: Prentice Hall (1981-09)
ISBN: 0131524623
EAN: 9780131524620
Dewey Decimal #: 519
Hardcover: 496 pages
SKU: 1001280034
Condition: Used: Very Good
Comments: clean with prior owner's name on interior cover page otherwise unmarked, light rubs
|
Editorial Reviews
|
Product 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. 1982 ed.
|
Customer Reviews
|
helpful and easy to read
Rating  (5)
Date: 2008-05-04
0 out of 1 customers found this reveiw helpful
I read the book and found it very helpful. It has a very excellent point of view and very easy to understand.
|
|
Well written
Rating  (4)
Date: 2007-04-05
1 out of 1 customers found this reveiw helpful
I bought this book because I wanted to have theory on linear programming including duality, integer linear programming, typical graph algorithms and matroid theory in one book. Up to now I have read only most of the chapter on matroids and I would like to say a big thanks to the author.
Although you will not solve the world's problems with greedy algorithms, my mathematical part of the heart was pleased and satisfied by the theory which explained the very nice relation between matroids and greedy algorithms.
Maybe I will tell you more in a few months
|
|
Combinatorial Optimization: Algorithms and Complexity
Rating (5)
Date: 2007-02-18
1 out of 7 customers found this reveiw helpful
The book's state is very good, so I am satisfied with it.
|
|
A classic...
Rating (5)
Date: 2007-01-11
2 out of 2 customers found this reveiw helpful
I won't lie to you: this book is well written but relatively hard to read. The subject is inherently difficult, after all! I highly suggest it, though, because the author is a recognized expert on the field and the price is relatively low. It's worth it even if you enjoy a few pages...
|
|
Mmm, algorithms....
Rating (5)
Date: 2006-11-11
5 out of 5 customers found this reveiw helpful
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.
|
|
|
|
|