Lecture Notes on

Approximation Algorithms for Network Problems

by J.Cheriyan* and R.Ravi^

* Dept. of Combinatorics and Optimization, University of Waterloo, Canada.     jcheriyan@uwaterloo.ca
^ GSIA, Carnegie Mellon University, Pittsburgh, USA.     ravi@cmu.edu

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