Designing networks incrementally

Conference Paper

We consider the problem of incrementally designing a network to route demand to a single sink on an underlying metric space. We are given cables whose costs per unit length scale in a concave fashion with capacity. Under certain natural restrictions on the costs (called the Access Network Design constraints), we present a simple and efficient randomized algorithm that is competitive to the minimum cost solution when the demand points arrive online. In particular, if the order of arrival is a random permutation, we can prove a O(1) competitive ratio. For the fully adverserial case, the algorithm is O(K)-competitive, where K is the number of different pipe types. Since the value of K is typically small, this improves the previous O(log n loglog n)-competitive algorithm which was based on probabilistically approximating the underlying metric by a tree metric. Our algorithm also improves the best known approximation ratio and running time for the offline version of this problem.

Full Text

Duke Authors

Cited Authors

  • Meyerson, A; Munagala, K; Plotkin, S

Published Date

  • January 1, 2001

Published In

Start / End Page

  • 406 - 415

International Standard Serial Number (ISSN)

  • 0272-5428

Digital Object Identifier (DOI)

  • 10.1109/sfcs.2001.959915

Citation Source

  • Scopus