Computer Science Department
School of Computer Science, Carnegie Mellon University
Online Algorithms for Network Design
Adam Meyerson
February 2003
CMU-CS-03-115.ps
CMU-CS-03-115.pdf
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 This page maintained by reports@cs.cmu.edu
School of Computer Science homepage