Please send any feedback on the correctness, content, and style of these notes via email to firstname.lastname@example.org or to email@example.com.
A copy of all the chapters may be found here (postscript file, 850 KB, 214 pages).
Table of Contents ( text or postscript).
In the current draft, each of the chapters may be read almost independently of the others. Here are the individual chapters in the form of gzipped postscript files.
Basics Basics graph theory definitions, shortest paths The set covering problem greedy heuristic, LP relaxation, approximation guarantee
Network Design Minimum spanning trees optimality conditions, algorithms, LP formulation of Edmonds LASTs Light approximate shortest path trees Steiner trees the Steiner tree problem Constrained-forest problems Goemans-Williamson algorithm Minimum k-connected spanning subgraphs emphasis on the case of uniform edge weights
Facility Location Problems Center and median problems definitions, heuristics, Lin-Vitter algorithm Uncapacitated facility location (UFL) Aardal, Shymos and Tardos algorithm
Near-Optimal Cuts of Graphs Minimum cuts mincut algorithm, flow / cut-equivalent trees, k-cuts, and node multiway cuts Balanced separators of graphs Leighton-Rao algorithm for sparsest cuts and related topics
Bicriteria Approximation Bicriteria approximation algorithms for network design problems basic notions, a general method for similar objectives, diameter-bounded minimum spanning trees