## Designing networks incrementally

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.

### Duke Scholars

## Published In

## DOI

## ISSN

## Publication Date

## Start / End Page

### Citation

*Annual Symposium on Foundations of Computer Science - Proceedings*(pp. 406–415). https://doi.org/10.1109/sfcs.2001.959915

*Annual Symposium on Foundations of Computer Science - Proceedings*, 406–15, 2001. https://doi.org/10.1109/sfcs.2001.959915.

*Annual Symposium on Foundations of Computer Science - Proceedings*, 2001, pp. 406–15.

*Scopus*, doi:10.1109/sfcs.2001.959915.