Approximation algorithms for network design problems

This thesis describes approximation algorithms for a variety of aggregation problems. Determination of low cost aggregations of demands is a critical component of network design, and has been the subject of a great deal of study in the Operations Research community. The results described herein include the first polynomial-time algorithms to obtain results provably within a constant of the best-possible for the buy-at-bulk network design problem and several of its relatives. The thesis also includes the first treatment of network design problems from the perspective of online algorithms, giving online competitive routines for updating an existing aggregation structure to accommodate new demands over time. Additional results include approximation algorithms for new variants of facility location and a logarithmic approximation to the single-sink concave-cost flow problem.