Leighton-Rao might be practical: faster approximation algorithms for concurrent flow with uniform capacities

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Leighton-Rao might be practical: faster approximation algorithms for concurrent flow with uniform capacities

Full text

Pdf (1.15 MB)

Source

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

Baltimore, Maryland, United States

Pages: 310 - 321

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

P. Klein	Computer Science Department, Brown University, Providence, RI
C. Stein	Laboratory for Computer Science, MIT, Cambridge, MA
É. Tardos	School of Operations Research, Cornell University Ithaca, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/100216.100257 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 B. Dial, Algorithm 360: shortest-path forest with topological ordering [H], Communications of the ACM, v.12 n.11, p.632-633, Nov. 1969 [doi>10.1145/363269.363610]
	2	Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
	3	A. V. Goldberg and R. E. Tarjan. finding minimumcost circulations by successive approximation. Technical Report MIT/LCS/TM-333, Laboratory for Computer Science, M.I.T., 1987. (Math. of Oper. Res., to appear).
	4	S Kapoor , P M Vaidya, Fast algorithms for convex quadratic programming and multicommodity flows, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.147-159, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12145]
	5	P. Klein and C. Stein. Leighton-Rao might be practical: a faster approximation algorithm for uniform concurrent flow. Unpublished manuscript, November 1989.
	6	F. T. Leighton, November 1989. Private communication.
	7	T. Leighton and S. Rao. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 422-431. IEEE, October 1988.
	8	P. Raghavan. Probabilistic construction of deterministic algorithms: approximating packing integer programs. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pages 10- 18, 1986.
	9	P Raghavan , C D Thompson, Provably good routing in graphs: regular arrays, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.79-87, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22154]
	10	F. Shahrokhi and D. W. Matula. The maximum concurrent flow problem. Technical Reprot CSR-283, New Mexico Tech., 1988.
	11	Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
	12	E. Tardos. Improved approximation algorithm for concurrent multi-commodity flows. Technical Report 872, School of Operations Research and Industrial Engineering, Cornell University, October 1989.
	13	P. M. Valdya. Speeding up finear programming using fast matrix multiplication. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pages 332-337, 1989.

CITED BY 10

	Kevin Lang , Satish Rao, Finding near-optimal cuts: an empirical evaluation, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.212-221, January 25-27, 1993, Austin, Texas, United States
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	András A. Benczúr , David R. Karger, Approximating s-t minimum cuts in Õ(n²) time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.47-55, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis, Approximate max-flow min-(multi)cut theorems and their applications, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.698-707, May 16-18, 1993, San Diego, California, United States
	Tomasz Radzik, Fast deterministic approximation for the multicommodity flow problem, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.486-492, January 22-24, 1995, San Francisco, California, United States
	Philip N. Klein , S. Sairam, A parallel randomized approximation scheme for shortest paths, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.750-758, May 04-06, 1992, Victoria, British Columbia, Canada
	David R. Karger , Clifford Stein, An Õ(n²) algorithm for minimum cuts, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.757-765, May 16-18, 1993, San Diego, California, United States
	David R. Karger, Random sampling in cut, flow, and network design problems, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.648-657, May 23-25, 1994, Montreal, Quebec, Canada
	Satish B. Rao, Faster algorithms for finding small edge cuts in planar graphs, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.229-240, May 04-06, 1992, Victoria, British Columbia, Canada
	Tom Leighton , Clifford Stein , Fillia Makedon , Éva Tardos , Serge Plotkin , Spyros Tragoudas, Fast approximation algorithms for multicommodity flow problems, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.101-111, May 05-08, 1991, New Orleans, Louisiana, United States