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