These notes are not in a polished form, especially with respect to maintaining consistent notation and cross-references across the chapters. There may be some nontrivial errors, and no doubt there are typos and grammaticial errors. Also, our discussion of the literature and citation of the references is biased by our own interests; we apologize for any omissions and inaccuracies.

Please send any feedback on the correctness, content, and style of these notes via email to jcheriyan@uwaterloo.ca or to ravi@cmu.edu.

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 (PDF file) 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