# 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