A constant factor approximation for the single sink edge installation problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A constant factor approximation for the single sink edge installation problems

Full text

Pdf (182 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-third annual ACM symposium on Theory of computing table of contents

Hersonissos, Greece

Pages: 383 - 388

Year of Publication: 2001

ISBN:1-58113-349-9

Authors

Sudipto Guha	AT&T Research, Department of Computer Science, Stanford University, CA
Adam Meyerson	Department of Computer Science, Stanford University, CA
Kamesh Munagala	Department of Computer Science, Stanford University, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 35, Citation Count: 12

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/380752.380827 What is a DOI?

ABSTRACT

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Matthew Andrews , Lisa Zhang, The Access Network Design Problem, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.40, November 08-11, 1998
	2	B. Awerbuch , Y. Azar, Buy-at-bulk network design, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.542, October 19-22, 1997
	3	Baruch Awerbuch , Alan Baratz , David Peleg, Cost-sensitive analysis of communication protocols, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.177-187, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93417]
	4	Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
	5	Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
	6	Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha, Rounding via trees: deterministic approximation algorithms for group Steiner trees and k-median, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.114-123, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276719]
	7	Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha , Serge Plotkin, Approximating a Finite Metric by a Small Number of Tree Metrics, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.379, November 08-11, 1998
	8	Naveen Garg , Rohit Khandekar , Goran Konjevod , R. Ravi , F. S. Salman , Amitabh Sinha, On the Integrality Gap of a Natural Formulation of the Single-Sink Buy-at-Bulk Network Design Problem, Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.170-184, June 13-15, 2001
	9	S. Guha , A. Meyerson , K. Munagala, Hierarchical placement and network design problems, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.603, November 12-14, 2000
	10	D. R. Karget , M. Minkoff, Building Steiner trees with incomplete global knowledge, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.613, November 12-14, 2000
	11	S. Khuller, B. Raghavachari, and N. Young. Balancing minimum spanning and shortest path trees. Algorithmica, 14(4):305-321, 1994.
	12	A. Meyerson , K. Munagala , S. Plotkin, Cost-distance: two metric network design, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.624, November 12-14, 2000
	13	F. S. Salman , J. Cheriyan , R. Ravi , S. Subramanian, Buy-at-bulk network design: approximating the single-sink edge installation problem, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.619-628, January 05-07, 1997, New Orleans, Louisiana, United States

CITED BY 12

	Ashish Goel , Deborah Estrin, Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Anupam Gupta , Amit Kumar , Tim Roughgarden, Simpler and better approximation algorithms for network design, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Moses Charikar , Adriana Karagiozova, On non-uniform multicommodity buy-at-bulk network design, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Julia Chuzhoy , Anupam Gupta , Joseph (Seffi) Naor , Amitabh Sinha, On the approximability of some network design problems, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Anupam Gupta , Mohammad T. Hajiaghayi , Harald Räcke, Oblivious network design, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.970-979, January 22-26, 2006, Miami, Florida
	Sudipto Guha , Adam Meyerson , Kamesh Munagala, A constant factor approximation algorithm for the fault-tolerant facility location problem, Journal of Algorithms, v.48 n.2, p.429-440, September 2003
	Anupam Gupta , Amit Kumar , Martin P´al , Tim Roughgarden, Approximation via cost sharing: Simpler and better approximation algorithms for network design, Journal of the ACM (JACM), v.54 n.3, p.11-es, June 2007
	Julia Chuzhoy , Anupam Gupta , Joseph (Seffi) Naor , Amitabh Sinha, On the approximability of some network design problems, ACM Transactions on Algorithms (TALG), v.4 n.2, p.1-17, May 2008
	Zoya Svitkina, Lower-bounded facility location, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1154-1163, January 20-22, 2008, San Francisco, California
	C. Chekuri , M. T. Hajiaghayi , G. Kortsarz , M. R. Salavatipour, Approximation algorithms for node-weighted buy-at-bulk network design, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1265-1274, January 07-09, 2007, New Orleans, Louisiana
	Raja Jothi , Balaji Raghavachari, Improved approximation algorithms for the single-sink buy-at-bulk network design problems, Journal of Discrete Algorithms, v.7 n.2, p.249-255, June, 2009
	Anupam Gupta , Amit Kumar, A constant-factor approximation for stochastic Steiner forest, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA