Computer Science Department
School of Computer Science, Carnegie Mellon University
Online Algorithms for Network Design
Keywords: Online algorithms, network design, approximation algorithms,
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.