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}