Randomized metarounding (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Randomized metarounding (extended abstract)

Full text

Pdf (436 KB)

Source

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

Portland, Oregon, United States

Pages: 58 - 62

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Robert Carr	Sandia National Labs, Albuquerque NM
Santosh Vempala	Dept. of Mathematics, M.I.T., Cambridge MA

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): 25, Citation Count: 8

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/335305.335312 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	Robert D. Carr , Santosh Vempala, Towards a 4/3 approximation for the asymmetric traveling salesman problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.116-125, January 09-11, 2000, San Francisco, California, United States
	2	Joseph Cheriyan , András Sebö , Zoltán Szigeti, An Improved Approximation Algorithm for Minimum Size 2-Edge Connected Spanning Subgraphs, Proceedings of the 6th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.126-136, June 22-24, 1998
	3	Torben Hagerup , C. Rüb, A guided tour of Chernoff bounds, Information Processing Letters, v.33 n.6, p.305-308, February 1990 [doi>10.1016/0020-0190(90)90214-I]
	4	Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
	5	P. Raghavan and C. Thompson. Multiterminal global routing: a deterministic approximation scheme. Algorithrnica, 6:73-82, 1991.
	6	Santosh Vempala , Berthold Vöcking, Approximating Multicast Congestion, Proceedings of the 10th International Symposium on Algorithms and Computation, p.367-372, December 16-18, 1999

CITED BY 8

	Anna Moss , Yuval Rabani, Approximation algorithms for constrained for constrained node weighted steiner tree problems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.373-382, July 2001, Hersonissos, Greece
	Kamal Jain , Mohammad Mahdian , Mohammad R. Salavatipour, Packing Steiner trees, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Peter Sanders , Sebastian Egner , Ludo Tolhuizen, Polynomial time algorithms for network information flow, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	SingLing Lee , Hann-Jang Ho, On minimizing the maximum congestion for Weighted Hypergraph Embedding in a Cycle, Information Processing Letters, v.87 n.5, p.271-275, 15 September 2003
	Randeep Bhatia , Li (Erran) Li, Characterizing achievable multicast rates in multi-hop wireless networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA
	SingLing Lee , Hann-Jang Ho, A 1.5 Approximation Algorithm for Embedding Hyperedges in a Cycle, IEEE Transactions on Parallel and Distributed Systems, v.16 n.6, p.481-488, June 2005
	Tamás Terlaky , Anthony Vannelli , Hu Zhang, On routing in VLSI design and communication networks, Discrete Applied Mathematics, v.156 n.11, p.2178-2194, June, 2008
	Peng-Jun Wan, Multiflows in multihop wireless networks, Proceedings of the tenth ACM international symposium on Mobile ad hoc networking and computing, May 18-21, 2009, New Orleans, LA, USA