Design networks with bounded pairwise distance

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Design networks with bounded pairwise distance

Full text

Pdf (882 KB)

Source

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

Atlanta, Georgia, United States

Pages: 750 - 759

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Yevgeniy Dodis	Massachusetts Institute of Technology
Sanjeev Khanna	Bell Labs

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 50, Citation Count: 15

Additional Information:

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

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	Ingo Althöfer , Gautam Das , David Dobkin , Deborah Joseph , José Soares, On sparse spanners of weighted graphs, Discrete & Computational Geometry, v.9 n.1, p.81-100, 1993 [doi>10.1007/BF02189308]
	2	Edoardo Amaldi , Viggo Kann, The complexity and approximability of finding maximum feasible subsystems of linear relations, Theoretical Computer Science, v.147 n.1-2, p.181-210, Aug. 7, 1995 [doi>10.1016/0304-3975(94)00254-G]
	3	Sanjeev Arora , László Babai , Jacques Stern , Z. Sweedyk, The hardness of approximate optima in lattices, codes, and systems of linear equations, Journal of Computer and System Sciences, v.54 n.2, p.317-331, April 1997 [doi>10.1006/jcss.1997.1472]
	4	Sanjeev Arora , Madhu Sudan, Improved low-degree testing and its applications, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.485-495, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258642]
	5	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]
	6	Moses Charikar , Chandra Chekuri , To-yat Cheung , Zuo Dai , Ashish Goel , Sudipto Guha , Ming Li, Approximation algorithms for directed Steiner problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.192-200, January 25-27, 1998, San Francisco, California, United States
	7	E. Cohen. Fast Algorithms for constructing t-spanners and paths with stretch t (extended abstract). In Proc. 34th Syrup. on Foundation of Computer Science, pp. 648-658, 1993.
	8	Uriel Feige, A threshold of ln n for approximating set cover (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.314-318, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237977]
	9	Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	10	Sanjeev Khanna , Madhu Sudan , Luca Trevisan, Constraint Satisfaction: The Approximability of Minimization Problems, Proceedings of the 12th Annual IEEE Conference on Computational Complexity, p.282, June 24-27, 1997
	11	Samir Khuller , Balaji Raghavachari , Neal Young, Balancing minimum spanning and shortest path trees, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.243-250, January 25-27, 1993, Austin, Texas, United States
	12	Guy Kortsarz, On the Hardness of Approximation Spanners, Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization, p.135-146, July 18-19, 1998
	13	Guy Kortsarz , David Peleg, Generating Sparse 2-spanners, Proceedings of the Third Scandinavian Workshop on Algorithm Theory, p.73-82, July 08-10, 1992
	14	Guy Kortsarz , David Peleg, Generating low-degree 2-spanners, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.556-563, January 23-25, 1994, Arlington, Virginia, United States
	15	Guy Kortsarz , David Peleg, Approximating shallow-light trees, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.103-110, January 05-07, 1997, New Orleans, Louisiana, United States
	16	E. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, 1976.
	17	C. Li, S. McCormick, and D. Simchi-Levi. On the Minimum-cardinality-bounded-diameter and Boundedcardinality-minimum-diameter Edge Addition Problems. In Operation Research Letters, 11:303-308, 1992.
	18	Madhav V. Marathe , R. Ravi , Ravi Sundaram , S. S. Ravi , Daniel J. Rosenkrantz , Harry B. Hunt, III, Bicriteria network design problems, Journal of Algorithms, v.28 n.1, p.142-171, July 1, 1998 [doi>10.1006/jagm.1998.0930]
	19	R. Ravi , M. V. Marathe , S. S. Ravi , D. J. Rosenkrantz , H. B. Hunt, III, Many birds with one stone: multi-objective approximation algorithms, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.438-447, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167209]
	20	R. Ravi , R. Sundaram , M. V. Marathe , D. J. Rosenkrantz , S. S. Ravi, Spanning trees short or small, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.546-555, January 23-25, 1994, Arlington, Virginia, United States
	21	Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258641]

CITED BY 15

	Michael Elkin , David Peleg, (1 + &egr;&Bgr;)-spanner constructions for general graphs, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.173-182, July 2001, Hersonissos, Greece
	Alberto Caprara , Giuseppe F. Italiano , G. Mohan , Alessandro Panconesi , Aravind Srinivasan, Wavelength rerouting in optical networks, or the Venetian Routing problem, Journal of Algorithms, v.45 n.2, p.93-125, November 2002
	Robert D. Carr , Srinivas Doddi , Goran Konjevod , Madhav Marathe, On the red-blue set cover problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.345-353, January 09-11, 2000, San Francisco, California, United States
	Michael Elkin , Guy Kortsarz, Logarithmic inapproximability of the radio broadcast problem, Journal of Algorithms, v.52 n.1, p.8-25, July 2004
	Michael Elkin , Guy Kortsarz, Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Eric Rosenberg, Hierarchical topological network design, IEEE/ACM Transactions on Networking (TON), v.13 n.6, p.1402-1409, December 2005
	Guy Kortsarz , Zeev Nutov, Tight approximation algorithm for connectivity augmentation problems, Journal of Computer and System Sciences, v.74 n.5, p.662-670, August, 2008
	R. C. Chakinala , A. Kumarasubramanian , K. A. Laing , R. Manokaran , C. Pandu Rangan , R. Rajaraman, Playing push vs pull: models and algorithms for disseminating dynamic data in networks, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Yon Dourisboure , Feodor F. Dragan , Cyril Gavoille , Chenyu Yan, Spanners for bounded tree-length graphs, Theoretical Computer Science, v.383 n.1, p.34-44, September, 2007
	Arnab Bhattacharyya , Elena Grigorescu , Kyomin Jung , Sofya Raskhodnikova , David P. Woodruff, Transitive-closure spanners, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.932-941, January 04-06, 2009, New York, New York
	Chandra Chekuri, Routing and network design with robustness to changing or uncertain traffic demands, ACM SIGACT News, v.38 n.3, September 2007
	Chandra Chekuri , Guy Even , Anupam Gupta , Danny Segev, Set connectivity problems in undirected graphs and the directed Steiner network problem, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.532-541, January 20-22, 2008, San Francisco, California
	Li Lao , Jun-Hong Cui , Mario Gerla , Shigang Chen, A Scalable Overlay Multicast Architecture for Large-Scale Applications, IEEE Transactions on Parallel and Distributed Systems, v.18 n.4, p.449-459, April 2007
	Moran Feldman , Guy Kortsarz , Zeev Nutov, Improved approximating algorithms for Directed Steiner Forest, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.922-931, January 04-06, 2009, New York, New York
	Yuval Lando , Zeev Nutov, Inapproximability of survivable networks, Theoretical Computer Science, v.410 n.21-23, p.2122-2125, May, 2009