# A constant factor approximation for the single sink edge installation problem

Conference Paper

We present the first constant approximation to the single sink buy-at-bulk network design problem, where we have to design a network by buying pipes of different costs and capacities per unit length to route demands at a set of sources to a single sink. The distances in the underlying network form a metric. This result improves the previous bound of O(log |R|), where R is the set of sources. Our algorithms are combinatorial and can be derandomized easily at the cost of a constant factor loss in the approximation ratio.

### Duke Authors

### Cited Authors

- Guha, S; Meyerson, A; Munagala, K

### Published Date

- September 29, 2001

### Published In

### Start / End Page

- 383 - 388

### International Standard Serial Number (ISSN)

- 0734-9025

### Citation Source

- Scopus