A Combinatorial Optimization Primer

Notes by Brian Mortimer, 2001

These notes were prepared for a third-year (Junior) level course in combinatorial optimization. They can be downloaded as a bundle or by chapter. Several parts remain to be written. Please feel free to use these materials for education, teaching and learning.

Download all chapters

Table of Contents (pdf file)

Chapter 0. Introduction (Not yet written)

Chapter 1. Minimum Weight Paths and Spanning Trees (pdf file)
1.1 Basic Ideas
1.2 Non-negative Weights
1.3 The General Case
1.4 Predecessor Subgraph and Negative Weight Cycles
1.5 Examples
1.6 Minimum Weight Spanning Trees

Chapter 2.Maximum Flow in a Network (pdf file)

Interlude: Linear Programming Formulations of Some Combinatorial Optimization Problems (pdf file)

Chapter 3. Maximum Flow by Pre-flow Push (pdf file)
3.1 Pre-flows and Distance Labellings
3.2 Preflow Push Algorithms
3.3 Performance

Chapter 4. Min-cost Flows (pdf file)
4.1 Minimum Cost Flow Problems
4.2 The Incremental Network
4.3 An Algorithm for Min-cost Flow
4.4 Network Simplex Algorithm

References (pdf file) and LINK