You are here

Combinatorial Optimization: Theory and Algorithms

Bernhard Korte and Jens Vygen
Springer Verlag
Publication Date: 
Number of Pages: 
Algorithms and Combinatorics 21
[Reviewed by
Brian Borchers
, on

This volume is an encyclopedic reference and textbook on theory and algorithms in combinatorial optimization. The authors give theoretical results and algorithms for the solution of linear and integer programming, minimum spanning tree, maximum flow, minimum cost flow, multicommodity flow, traveling salesman, network design, facility location, matching, matroid optimization, knapsack, and bin packing problems. The authors also provide an introduction to computational complexity, NP-Completeness, and approximation algorithms.

The focus is on deterministic algorithms for the solution of these combinatorial optimization problems. There is very little discussion of heuristic approaches and randomized algorithms. The book follows a mathematical programming approach rather than an approach grounded in computer science.

The scope of this work is vast, so that the presentation is necessarily concise. For example, the simplex algorithm for linear programming is covered in only four pages. If this book is used as the textbook for an introductory course in combinatorial optimization the instructor will need to supplement the book with extensive lecture notes. Compare this book with Lee's A First Course in Combinatorial Optimization or Combinatorial Optimization by Cook, Cunningham, Pulleyblank, and Schrijver, both of which introduce key ideas in combinatorial optimization in a much more accessible fashion.

As befits a reference book, the references are very complete and up to date. Rather than a single large bibliography, there is a separate list of references for each chapter. The book has separate topic and author indexes and a very useful glossary of notation. The authors should also be commended for providing an errata sheet with corrections for a few errors that have been found in the book. ( )

Another recent reference book in this area is the massive three volume set, Combinatorial Optimization: Polyhedra and Efficiency by Schrijver. Schrijver's book covers the same topics as Korte and Vygen, with even more detail. However, Schrijver's book has no exercises and is not intended for use as a textbook.

The book by Korte and Vygen will appeal primarily to readers who want an advanced textbook that can also serve as a concise reference. For many years, the standard advanced textbook and reference in combinatorial optimization was Integer and Combinatorial Optimization by Nemhauser and Wolsey. The current volume by Korte and Vygen is a worthy successor.


William J. Cook, William H. Cunningham, William R. Pulleyblank, and Alexander Schrijver, Combinatorial Optimization , Wiley-Interscience, 1997.

John Lee, A First Course in Combinatorial Optimization , Cambridge University Press, 2004.

Alexander Schrijver, Combinatorial Optimization , Springer 2003.

Laurence A. Wolsey and George L. Nemhauser, Integer and Combinatorial Optimization , Wiley-Interscience, 1988.

Brian Borchers is a professor of Mathematics at the New Mexico Institute of Mining and Technology. His interests are in optimization and applications of optimization in parameter estimation and inverse problems. 

 Preface.- Introduction.- Graphs.- Linear Programming.- Linear Programming Algorithms.- Integer Programming.- Spanning Trees and Arborescences.- Shortest Paths.- Network Flows.- Minimum Cost Flows.- Maximum Matchings.- Weighted Matching.- b-Matchings and T-Joins.- Matroids.- Generalizations of Matroids.- NP-Completeness.- Approximation Algorithms.- The Knapsack Problem.- Bin Packing.- Multicommodity Flows and Edge-Disjoint Paths.- Network Design Problems.- The Traveling Salesman Problem.- Facility Location.- Notation Index.- Author Index.- Subject Index.