Издательство Dover Publications, 1998, -528 pp.
During the fifteen years since Combinatorial Optimization first appeared, its authors have often discussed the possibility of a second edition. In some sense a second edition seemed very appropriate, even called for. Many exciting new results had appeared that would merit inclusion, while not quite so many and so exciting that the basic premises, style, and approach of the book would need to be reworked.
The current republication of the book by Dover gives us an interesting opportunity to look critically at the book, and the field it recounts, fifteen years later. In retrospect, we are now happy with our decision (if you can call it that) not to proceed with a second edition. This was a book about two fields, at a moment when they had reached a degree of joint maturity and cross-fertilization that can inspire and justify a book; this feeling of novelty and timeliness would have been lost in a second edition. It is so much more appropriate (and, quite frankly, fun) to contemplate the interim developments from the armchair of a preface-writer.
The goal of this book is to bring, together in one volume the important ideas of computational complexity developed by computer scientists over the past fifteen years, and the foundations of mathematical programming, developed by the operations research community. The tint seven chapters comprise a self-contained treatment of linear programming and duality theory, with an emphasis on graph and network flow interpretations. Chapter 8 is a transition chapter which introduces the techniques for analyzing the complexity of algorithms. Mode, fast algorithms for flow, matching, and spanning, trees, as wen as the general setting, of matroids, are described in Chapters 9-
12. The next two chapters, 13 and 14, treat integer linear programming, including, Gomory's Cutting-plane algorithm. Chapters 15-16 take up the relatively new ideas of the theory of NP-completeness and its ramifications. The last three chapters, 17-19, describe practical ways of dealing, with intractable problems - approximation algorithms, branch-and-bound, dynamic programming and local (or neighborhood) search.
Optmization Problems.
The Simplex Algorithm.
Duauty.
Computanonal Considerations for the Simplex Algorithm.
The Primal-Dual Algorithm.
Primal-Dual Algorithms for Max-Flow and Shortest Path: Ford-Fulkerson and Dijkstra.
Primal-Dual Algorithms for Min-Cost Flow.
Algorithms and Complexity.
Efficient Algorithms for the Max-Flow Problem.
Algorithms for Matching.
Weighted Matching.
Spanning Trees and Matroids.
Integer Linear Programming.
A Cutting-Plane Algorithm for Integer Linear Programs.
NP-Complete Problems.
More about NP-Completeness.
Approximation Algorithms.
Branch-and-Bound and Dynamic Programming.
Local Search.
During the fifteen years since Combinatorial Optimization first appeared, its authors have often discussed the possibility of a second edition. In some sense a second edition seemed very appropriate, even called for. Many exciting new results had appeared that would merit inclusion, while not quite so many and so exciting that the basic premises, style, and approach of the book would need to be reworked.
The current republication of the book by Dover gives us an interesting opportunity to look critically at the book, and the field it recounts, fifteen years later. In retrospect, we are now happy with our decision (if you can call it that) not to proceed with a second edition. This was a book about two fields, at a moment when they had reached a degree of joint maturity and cross-fertilization that can inspire and justify a book; this feeling of novelty and timeliness would have been lost in a second edition. It is so much more appropriate (and, quite frankly, fun) to contemplate the interim developments from the armchair of a preface-writer.
The goal of this book is to bring, together in one volume the important ideas of computational complexity developed by computer scientists over the past fifteen years, and the foundations of mathematical programming, developed by the operations research community. The tint seven chapters comprise a self-contained treatment of linear programming and duality theory, with an emphasis on graph and network flow interpretations. Chapter 8 is a transition chapter which introduces the techniques for analyzing the complexity of algorithms. Mode, fast algorithms for flow, matching, and spanning, trees, as wen as the general setting, of matroids, are described in Chapters 9-
12. The next two chapters, 13 and 14, treat integer linear programming, including, Gomory's Cutting-plane algorithm. Chapters 15-16 take up the relatively new ideas of the theory of NP-completeness and its ramifications. The last three chapters, 17-19, describe practical ways of dealing, with intractable problems - approximation algorithms, branch-and-bound, dynamic programming and local (or neighborhood) search.
Optmization Problems.
The Simplex Algorithm.
Duauty.
Computanonal Considerations for the Simplex Algorithm.
The Primal-Dual Algorithm.
Primal-Dual Algorithms for Max-Flow and Shortest Path: Ford-Fulkerson and Dijkstra.
Primal-Dual Algorithms for Min-Cost Flow.
Algorithms and Complexity.
Efficient Algorithms for the Max-Flow Problem.
Algorithms for Matching.
Weighted Matching.
Spanning Trees and Matroids.
Integer Linear Programming.
A Cutting-Plane Algorithm for Integer Linear Programs.
NP-Complete Problems.
More about NP-Completeness.
Approximation Algorithms.
Branch-and-Bound and Dynamic Programming.
Local Search.