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

Publication
, Conference

Guha, S; Meyerson, A; Munagala, K

Published in: Conference Proceedings of the Annual ACM Symposium on Theory of Computing

September 29, 2001

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 Scholars

## Published In

Conference Proceedings of the Annual ACM Symposium on Theory of Computing

## ISSN

0734-9025

## Publication Date

September 29, 2001

## Start / End Page

383 / 388

### Citation

APA

Chicago

ICMJE

MLA

NLM

Guha, S., Meyerson, A., & Munagala, K. (2001). A constant factor approximation for the single sink edge installation problem. In

*Conference Proceedings of the Annual ACM Symposium on Theory of Computing*(pp. 383–388).Guha, S., A. Meyerson, and K. Munagala. “A constant factor approximation for the single sink edge installation problem.” In

*Conference Proceedings of the Annual ACM Symposium on Theory of Computing*, 383–88, 2001.Guha S, Meyerson A, Munagala K. A constant factor approximation for the single sink edge installation problem. In: Conference Proceedings of the Annual ACM Symposium on Theory of Computing. 2001. p. 383–8.

Guha, S., et al. “A constant factor approximation for the single sink edge installation problem.”

*Conference Proceedings of the Annual ACM Symposium on Theory of Computing*, 2001, pp. 383–88.Guha S, Meyerson A, Munagala K. A constant factor approximation for the single sink edge installation problem. Conference Proceedings of the Annual ACM Symposium on Theory of Computing. 2001. p. 383–388.

## Published In

Conference Proceedings of the Annual ACM Symposium on Theory of Computing

## ISSN

0734-9025

## Publication Date

September 29, 2001

## Start / End Page

383 / 388