Simpler and better approximation algorithms for network design

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Simpler and better approximation algorithms for network design

Full text

Pdf (153 KB)

Source

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

San Diego, CA, USA

SESSION: Session 7B table of contents

Pages: 365 - 372

Year of Publication: 2003

ISBN:1-58113-674-9

Authors

Anupam Gupta	Carnegie Mellon University, Pittsburgh, PA
Amit Kumar	Lucent Bell Labs, Murray Hill, NJ
Tim Roughgarden	Cornell University, Ithaca, NY

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 107, Citation Count: 24

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/780542.780597 What is a DOI?

ABSTRACT

We give simple and easy-to-analyze randomized approximation algorithms for several well-studied NP-hard network design problems. Our algorithms improve over the previously best known approximation ratios. Our main results are the following.

We give a randomized 3.55-approximation algorithm for the connected facility location problem. The algorithm requires three lines to state, one page to analyze, and improves the best-known performance guarantee for the problem.
We give a 5.55-approximation algorithm for virtual private network design. Previously, constant-factor approximation algorithms were known only for special cases of this problem.
We give a simple constant-factor approximation algorithm for the single-sink buy-at-bulk network design problem. Our performance guarantee improves over what was previously known, and is an order of magnitude improvement over previous combinatorial approximation algorithms for the problem.

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 and Lisa Zhang. Approximation algorithms for access network design. Algorithmica, 34(2):197--215, 2002. (Preliminary version in 39th FOCS, 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 , Yossi Azar , Yair Bartal, On-line generalized Steiner problem, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.68-74, January 28-30, 1996, Atlanta, Georgia, United States
	4	Yair Bartal. Competitive Analysis of Distributed On-line Problems --- Distributed Paging. PhD thesis, Tel-Aviv University, Israel, 1994.
	5	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
	6	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]
	7	Yair Bartal , Amos Fiat , Yuval Rabani, Competitive algorithms for distributed data management, Journal of Computer and System Sciences, v.51 n.3, p.341-358, Dec. 1995 [doi>10.1006/jcss.1995.1073]
	8	N. G. Duffield , Pawan Goyal , Albert Greenberg , Partho Mishra , K. K. Ramakrishnan , Jacobus E. van der Merive, A flexible model for resource management in virtual private networks, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.95-108, August 30-September 03, 1999, Cambridge, Massachusetts, United States
	9	J. Andrew Fingerhut , Subhash Suri , Jonathan S. Turner, Designing least-cost nonblocking broadband networks, Journal of Algorithms, v.24 n.2, p.287-309, Aug. 1997 [doi>10.1006/jagm.1997.0866]
	10	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
	11	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
	12	Sudipto Guha , Adam Meyerson , Kamesh Munagala, A constant factor approximation for the single sink edge installation problems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.383-388, July 2001, Hersonissos, Greece [doi>10.1145/380752.380827]
	13	Anupam Gupta , Jon Kleinberg , Amit Kumar , Rajeev Rastogi , Bulent Yener, Provisioning a virtual private network: a network design problem for multicommodity flow, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.389-398, July 2001, Hersonissos, Greece [doi>10.1145/380752.380830]
	14	Refael Hassin , R. Ravi , F. S. Salman, Approximation algorithms for a capacitated network design problem, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, p.167-176, September 05-08, 2000
	15	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
	16	Samir Khuller , An Zhu, The general Steiner tree-star problem, Information Processing Letters, v.84 n.4, p.215-220, 30 November 2002 [doi>10.1016/S0020-0190(02)00271-5]
	17	Tae Ung Kim, Timothy J. Lowe, Arie Tamir, and James E. Ward. On the location of a tree-shaped facility. Networks, 28(3):167--175, 1996.
	18	Amit Kumar , Anupam Gupta , Tim Roughgarden, A Constant-Factor Approximation Algorithm for the Multicommodity, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.333, November 16-19, 2002
	19	Youngho Lee, Yuping Chiu, and Jennifer Ryan. A branch and cut algorithm for a Steiner tree-star problem. INFORMS Journal on Computing, 8(3):194--201, 1996.
	20	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
	21	A. Meyerson, Designing Networks Incrementally, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.406, October 14-17, 2001
	22	Robert C. Prim. Shortest interconnection networks and some generalizations. Bell System Technical Journal, 36:1389--1401, 1957.
	23	Gabriel Robins , Alexander Zelikovsky, Improved Steiner tree approximation in graphs, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.770-779, January 09-11, 2000, San Francisco, California, United States
	24	F. S. Salman , J. Cheriyan , R. Ravi , S. Subramanian, Approximating the Single-Sink Link-Installation Problem in Network Design, SIAM Journal on Optimization, v.11 n.3, p.595-610, 2000 [doi>10.1137/S1052623497321432]
	25	Chaitanya Swamy , Amit Kumar, Primal-Dual Algorithms for Connected Facility Location Problems, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, p.256-270, September 17-21, 2002
	26	Kunal Talwar, The Single-Sink Buy-at-Bulk LP Has Constant Integrality Gap, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.475-486, May 27-29, 2002

CITED BY 24

	Nicole Immorlica , David Karger , Maria Minkoff , Vahab S. Mirrokni, On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Stefano Leonardi , Guido Schaefer, Cross-monotonic cost-sharing methods for connected facility location games, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA
	Adam Meyerson, Online algorithms for network design, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Stefano Leonardi , Guido Schäfer, Cross-monotonic cost sharing methods for connected facility location games, Theoretical Computer Science, v.326 n.1-3, p.431-442, 20 October 2004
	Friedrich Eisenbrand , Fabrizio Grandoni, An improved approximation algorithm for virtual private network design, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Anupam Gupta , Martin Pál , R. Ravi , Amitabh Sinha, Boosted sampling: approximation algorithms for stochastic optimization, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, 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
	Luca Becchetti , Jochen Könemann , Stefano Leonardi , M. Pál, Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy, 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
	Mohammad Taghi Hajiaghayi , Kamal Jain, The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.631-640, January 22-26, 2006, Miami, Florida
	Lisa Fleischer , Jochen Könemann , Stefano Leonardi , Guido Schäfer, Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	L. Becchetti , J. Könemann , S. Leonardi , M. Páal, Sharing the cost more efficiently: Improved approximation for multicommodity rent-or-buy, ACM Transactions on Algorithms (TALG), v.3 n.2, p.23-es, May 2007
	Pavan Nuggehalli , Vikram Srinivasan , Carla-Fabiana Chiasserini , Ramesh R. Rao, Efficient cache placement in multi-hop wireless networks, IEEE/ACM Transactions on Networking (TON), v.14 n.5, p.1045-1055, October 2006
	Gee-Swee Poo , Haibo Wang, Multi-path routing versus tree routing for VPN bandwidth provisioning in the hose model, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.6, p.1725-1743, April, 2007
	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
	Naveen Garg , Anupam Gupta , Stefano Leonardi , Piotr Sankowski, Stochastic analyses for online combinatorial optimization problems, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.942-951, January 20-22, 2008, San Francisco, California
	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
	Friedrich Eisenbrand , Fabrizio Grandoni , Thomas Rothvoß , Guido Schäfer, Approximating connected facility location problems via random facility sampling and core detouring, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1174-1183, 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
	Chandra Chekuri, Routing and network design with robustness to changing or uncertain traffic demands, ACM SIGACT News, v.38 n.3, September 2007
	Monia Ghobadi , Sudhakar Ganti , Gholamali C. Shoja, Resource optimization algorithms for virtual private networks using the hose model, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.52 n.16, p.3130-3147, November, 2008
	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
	R. Ravi , Amitabh Sinha, Approximation Algorithms for Problems Combining Facility Location and Network Design, Operations Research, v.54 n.1, p.73-81, January-February 2006