You are here

A First Course in Combinatorial Optimization

Jon Lee
Cambridge University Press
Publication Date: 
Number of Pages: 
Cambridge Texts in Applied Mathematics
[Reviewed by
William J. Satzer
, on

A First Course in Combinatorial Optimization is a textbook designed for a one-semester introduction at the first year graduate level.  It is aimed at students of mathematics, computer science, and operations research.  The treatment is largely self-contained, though more than a modest amount of "mathematical maturity" is expected of the reader. 

A combinatorial optimization problem involves maximizing a real-valued objective function on a finite set of feasible solutions S, wherein S arises as a subset of the power set of some finite ground set.  In principle, all the solutions can be enumerated, but that is usually impractical. 

Applications of combinatorial optimization are widespread, both in industrial and scientific settings.  Industrial applications include network design and routing, manufacturing and distribution, and the scheduling of airline crews.  In applied sciences such as combinatorial chemistry, for example, there are now very active applications, particularly for pharmaceuticals.  Discrete optimization also has significant connections to rest of mathematics and computer science, especially via graph theory and enumerative combinatorics.

The author's goal is to offer an attractive but rigorous introduction to the field.  The unifying thread throughout is the interplay of matroids, submodularity and polyhedral combinatorics.  Intentionally, the author has little so say about applications even as he admits they are the raison d'être of combinatorial optimization.  He says instead that interesting mathematics and algorithm engineering are justification enough.  From the reader's side, that is disappointing. It would have been valuable to know what the applications are for the various techniques, even if no additional details are given.

An initial chapter lays out basic material on polytopes and linear programming.  The major topics that follow are matroids and the greedy algorithm, graph matching, flows and cuts, and branch-&-bound methods.  Proofs are clear and complete.  It is all very tidy — but it also seems a bit sterile in the absence of applications.

The book is attractively laid out on the page and there are lots of good diagrams.  Algorithms are separated visually in special boxes and are easy to track down.  There are plenty of problems (short proofs) and exercises (calculations) and they are well integrated with the text.

Bill Satzer ( is a senior intellectual property scientist at 3M Company, having previously been a lab manager at 3M for composites and electromagnetic materials. His training is in dynamical systems and particularly celestial mechanics; his current interests are broadly in applied mathematics and the teaching of mathematics.
Introduction; 0. Polytopes and linear programming; 1. Matroids and the greedy algorithm; 2. Minimum-weight dipaths; 3. Matroid intersection; 4. Matching; 5. Flows and cuts; 6. Cutting planes; 7. Branch-&-bound; 8. Optimizing submodular functions; Appendix.