Lecture Notes on Approximation Algorithms for Network Problems
	by J. Cheriyan* and R. Ravi^

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

 {chapter}{ {1} Basic Graph Theory and Shortest-Paths Algorithms}{1}
{ {1.1}Graph theory terminology}{1}
{ {1.2} The running time of algorithms}{4}
{ {1.3}Shortest Paths Problems}{5}
 { {1.3.1} Bellman's inequalities, node potentials and reduced costs}{5}
 { {1.3.2} Shortest paths arborescence}{7}
 { {1.3.3}Dijkstra's algorithm}{8}
 { {1.3.4}The Floyd-Warshall algorithm}{9}

 {chapter}{ {2}The Set Covering Problem}{12}
{ {2.1} The problem and its complexity}{12}
{ {2.2} Applications}{14}
{ {2.3} The matrix reduction algorithm for set covering}{15}
{ {2.4} The greedy algorithm for set covering}{16}
{ {2.5} A performance guarantee for the greedy algorithm}{18}
{ {2.6} A direct analysis}{20}
{ {2.7} A randomized algorithm}{21}
{ {2.8} Exercises}{22}

 {chapter}{ {3} Center Problems and Median Problems}{25}
{ {3.1} Introduction}{25}
{ {3.2} The basic model for median problems and center problems}{26}
{ {3.3} Center problems \hskip 1em\relax (minimax problems)}{26}
 { {3.3.1} Multiple centers}{30}
{ {3.4} Median problems \hskip 1em\relax (minisum problems)}{30}
 { {3.4.1} A single-median algorithm}{32}
 { {3.4.2} A multimedian heuristic}{33}
{ {3.5}Bicriteria Approximations for the $k$-median Problem}{35}
 { {3.5.1} Introduction}{35}
 { {3.5.2}Hardness of approximation}{35}
 { {3.5.3}Rounding by filtering}{37}
 {Formulation}{37}
 {Filtering}{37}
 {Transformation to set covering}{38}
{ {3.6} Exercises}{39}

 {chapter}{ {4} The Uncapacitated Facility Location Problem}{46}
{ {4.1} The problem}{46}
{ {4.2} Applications}{47}
{ {4.3} Linear programming formulations of the UFL problem}{48}
{ {4.4} Duality}{49}
 { {4.4.1} First condensed dual}{49}
 { {4.4.2} Second condensed dual}{50}
{ {4.5} Heuristics for solving the UFL problem}{51}
 { {4.5.1} The greedy heuristic}{51}
 { {4.5.2} The dual descent procedure}{53}
{ {4.6} The filtering and rounding method for location problems}{57}
 { {4.6.1} Introduction}{57}
 { {4.6.2} An integer programming formulation for ``minimize'' UFL problems and its LP relaxation }{57}
 { {4.6.3} The Aardal-Shmoys-Tardos algorithm for ``minimize'' UFL problems}{58}
{ {4.7} Exercises}{61}

 {chapter}{ {5} Minimum Spanning Trees}{64}
{ {5.1}Applications}{64}
{ {5.2} Trees and cuts}{65}
{ {5.3} Minimum spanning trees}{66}
{ {5.4} Algorithms for minimum spanning trees}{67}
{ {5.5} LP formulation of the minimum spanning tree problem}{69}
{ {5.6} More LP formulations of the minimum spanning tree problem}{73}
{ {5.7} Exercises}{74}

 {chapter}{ {6} Light Approximate Shortest Paths Trees}{78}
{ {6.1} Introduction}{78}
{ {6.2} The preorder traversal of a tree}{78}
{ {6.3} An algorithm for finding a light approximate shortest-paths tree}{80}
{ {6.4} Exercises}{81}

 {chapter}{ {7}Approximation Algorithms for Steiner Trees}{84}
{ {7.1} The problem and its complexity}{84}
{ {7.2} Distance network heuristics for Steiner trees}{85}
 { {7.2.1} Introduction}{85}
 { {7.2.2} The basic distance network heuristic}{86}
 { {7.2.3} Mehlhorn's variant of the distance network heuristic}{89}
{ {7.3} The Dreyfus-Wagner dynamic programming algorithm}{92}
{ {7.4}Zelikovsky's Algorithm}{96}
 { {7.4.1}Definitions}{96}
 { {7.4.2}The algorithm}{96}
 { {7.4.3}Performance Guarantee}{97}
 { {7.4.4}Full Steiner Trees}{99}
{ {7.5} Exercises}{101}

 {chapter}{ {8}Constrained Forest Problems}{106}
{ {8.1} Constrained forest problems}{106}
{ {8.2} Proper functions}{107}
{ {8.3} Using proper functions to model problems in network design}{109}
{ {8.4}The LP relaxation of (IP)}{110}
{ {8.5}The GW algorithm for the constrained forests problem}{110}
{ {8.6} A performance guarantee for the GW algorithm}{113}
{ {8.7} Exercises}{119}

 {chapter}{ {9} Approximating minimum $k$-connected spanning subgraphs}{121}
{ {9.1} Introduction}{121}
{ {9.2} Definitions and notation}{122}
 { {9.2.1} Matching}{123}
{ {9.3} A 2-approximation algorithm for minimum weight $k$-ECSS}{123}
{ {9.4} An $O(1)$-approximation algorithm for minimum metric cost $k$-NCSS}{124}
{ {9.5}2-Approximation algorithms for minimum-size $k$-CSS}{126}
 { {9.5.1} An illustrative example}{127}
{ {9.6} Khuller and Vishkin's 1.5-approximation algorithm for minimum size 2-ECSS}{128}
{ {9.7}Mader's theorem and approximating minimum size 2-NCSS}{129}
{ {9.8} A $(1+{1\over {k}})$-approximation algorithm for minimum-size $k$-NCSS }{132}
{ {9.9} Mader's theorem}{134}
{ {9.10} Approximating minimum-size $k$-ECSS }{137}
{ {9.11} The multi edge model for minimum $k$-ECSS problems}{139}
{ {9.12} Bibliographic remarks}{140}
{ {9.13} Exercises}{141}

 {chapter}{ {10}Minimum cuts}{145}
{ {10.1}A simple minimum cut algorithm}{145}
 { {10.1.1}Introduction}{145}
 { {10.1.2}The Stoer-Wagner Algorithm}{147}
 { {10.1.3}A bound on the number of min cuts}{149}
{ {10.2}Gomory-Hu Trees: Existence}{150}
 { {10.2.1}Introduction}{150}
 { {10.2.2}Warm-up: Maximum spanning trees}{151}
{ {10.3}Gomory-Hu Trees: Construction}{152}
 { {10.3.1}Uncrossing cuts}{153}
 { {10.3.2}The construction algorithm}{156}
{ {10.4}Multicuts}{158}
 { {10.4.1}Introduction}{158}
 { {10.4.2}Two simple algorithms}{159}
 { {10.4.3}An efficient algorithm and analysis}{160}
{ {10.5}Multiway Cuts}{161}
 { {10.5.1}Introduction}{161}
 { {10.5.2}IP formulation of multiway cuts}{162}
 { {10.5.3}A half-integrality property}{165}
{ {10.6} Exercises}{168}

 {chapter}{ {11}Graph Separators}{172}
{ {11.1} The sparsest cut problem and an LP relaxation }{172}
{ {11.2} The sparsest cut problem: A region-growing algorithm }{175}
{ {11.3}The generalized sparsest cut problem}{179}
 { {11.3.1} Definitions and preliminaries}{180}
 { {11.3.2} $\ell _1$ embeddings and generalized sparsest cuts}{181}
{ {11.4} Bourgain's theorem }{185}
{ {11.5} From sparsest cuts to balanced separators}{187}
{ {11.6}Applications of separators}{188}
 { {11.6.1}Minimum cut linear arrangement}{189}
 { {11.6.2}Optimal linear arrangement}{190}
{ {11.7} Exercises}{191}

 {chapter}{ {12}Bicriteria Network Design problems}{196}
{ {12.1} Introduction}{196}
 { {12.1.1}Objective functions}{197}
 { {12.1.2}Performance guarantees}{197}
 { {12.1.3}Previous Work}{199}
{ {12.2}Hardness results}{200}
{ {12.3}Bicriteria Formulations: Simple Properties}{201}
 { {12.3.1}Equivalence of Bicriteria Formulations: Robustness}{201}
 { {12.3.2}Comparing with other functional combinations: Generality}{202}
{ {12.4}Parametric Search}{204}
{ {12.5}Diameter-Constrained Trees}{206}
{ {12.6} Exercises}{209}

 {chapter}{ {}{Index}}{214}