Computer Science Department
School of Computer Science, Carnegie Mellon University


Online Algorithms for Network Design

Adam Meyerson

February 2003

Keywords: Online algorithms, network design, approximation algorithms, concave-cost flow

We give the first polylogarithmic-competitive online algorithms for two-metric network design problems. These problems are very general, including as special cases such problems as steiner tree, facility location, and concave-cost single commodity flow.

12 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by