Fast approximation algorithms for multicommodity flow problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast approximation algorithms for multicommodity flow problems

Full text

Pdf (1.26 MB)

Source

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

New Orleans, Louisiana, United States

Pages: 101 - 111

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Tom Leighton	Department of Mathematics and Laboratory for Computer Science, MIT, Cambridge, MA
Clifford Stein	Laboratory for Computer Science, MIT, Cambridge, MA
Fillia Makedon	Computer Science Program, University of Texas at Dallas, Richardson, Texas
Éva Tardos	School of Operations Research, Cornell University, Ithaca, NY
Serge Plotkin	Department of Computer Science, Stanford University, Stanford, CA
Spyros Tragoudas	Computer Science Program, University of Texas at Dallas, Richardson, Texas

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 53, Citation Count: 20

Additional Information:

references cited by index terms review 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/103418.103425 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	R. K. Ahuja, A.V. Goldberg, J. B. Orlin, and R.E. Tarjan. Finding minimum cost flows by double scaling. Sloan Working Paper 204%88, MIT, Cambridge, MA, 1988.
	2	Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
	3	H. N. Gabow , R. E. Tarjan, Faster scaling algorithms for network problems, SIAM Journal on Computing, v.18 n.5, p.1013-1036, Oct. 1989 [doi>10.1137/0218069]
	4	A. V. Goldberg, Personal communication. Jan., 1991.
	5	Andrew V. Goldberg , Robert E. Tarjan, Finding minimum-cost circulations by successive approximation, Mathematics of Operations Research, v.15 n.3, p.430-466, Aug. 1990 [doi>10.1287/moor.15.3.430]
	6	L. R. Ford jr. and D. R. Fulkerson. Flows in networks. Princeton University Press, 1956.
	7	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]
	8	P. Klein, A. Agrawal, R. Ravi, and S. Rao. Approximation through multicommodity flow. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pages 726-727, 1990.
	9	P. Klein , C. Stein , É. Tardos, Leighton-Rao might be practical: faster approximation algorithms for concurrent flow with uniform capacities, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.310-321, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100257]
	10	T. Leighton and S. Rao. An approximate max-flow raincut 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, 1988.
	11	Fillia Makedon , Spyros Tragoudas, Approximating the minimum net expansion: near optimal solutions to circuit partitioning problems, Proceedings of the 16th international workshop on Graph-theoretic concepts in computer science, p.140-153, May 1991, Berlin, Germany
	12	James Orlin, A faster strongly polynomial minimum cost flow algorithm, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.377-387, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62249]
	13	Farhad Shahrokhi , D. W. Matula, The maximum concurrent flow problem, Journal of the ACM (JACM), v.37 n.2, p.318-334, April 1990 [doi>10.1145/77600.77620]
	14	P. M. Vaidya. Speeding up linear programming using fast matrix multiplication. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pages 332-337, 1989.
	15	M.A. Yakovleva. A problem on minimum transportation cost. in V.S. Nemchinov, editor, Applications of Mathematics in Economic Research, pages 390-399. Izdat. Social'no-Ekon. Lit., Moscow, 1959.

CITED BY 20

	James Aspnes , Yossi Azar , Amos Fiat , Serge Plotkin , Orli Waarts, On-line load balancing with applications to machine scheduling and virtual circuit routing, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.623-631, May 16-18, 1993, San Diego, California, United States
	Philip Klein , Hsueh-I Lu, Efficient approximation algorithms for semidefinite programs arising from MAX CUT and COLORING, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.338-347, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	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
	Guy Even , Joseph (Seffi) Naor , Satish Rao , Baruch Schieber, Fast approximate graph partitioning algorithms, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.639-648, January 05-07, 1997, New Orleans, Louisiana, 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
	Anil Kamath , Omri Palmon , Serge Plotkin, Fast approximation algorithm for minimum cost multicommodity flow, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.493-501, January 22-24, 1995, San Francisco, California, United States
	Serge A. Plotkin , Éva Tardos, Improved bounds on the max-flow min-cut ratio for multicommodity flows, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.691-697, 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
	David Bruce Wilson, Embedding leveled hypercube algorithms into hypercubes (extended abstract), Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.264-270, June 29-July 01, 1992, San Diego, California, United States
	Michael C. Loui, Strategic directions in research in theory of computing, ACM Computing Surveys (CSUR), v.28 n.4, p.575-590, Dec. 1996
	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
	Anil Kamath , Omri Palmon, Improved interior point algorithms for exact and approximate solution of multicommodity flow problems, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.502-511, January 22-24, 1995, San Francisco, California, United States
	Baruch Awerbuch , Tom Leighton, Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.487-496, May 23-25, 1994, Montreal, Quebec, Canada
	Martin Fürer , Balaji Raghavachari, Approximating the minimum degree spanning tree to within one from the optimal degree, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.317-324, September 1992, Orlando, Florida, United States
	Xiaotie Deng , Guojun Li , Wenan Zang , Yi Zhou, A 2-approximation algorithm for path coloring on a restricted class of trees of rings, Journal of Algorithms, v.47 n.1, p.1-13, April 2003
	Neal E. Young, Randomized rounding without solving the linear program, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.170-178, January 22-24, 1995, San Francisco, California, United States
	D. Bienstock , G. Iyengar, Solving fractional packing problems in O^ast(1/ε) iterations, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Baruch Awerbuch , David Holmer , Herbert Rubens, The medium time metric: high throughput route selection in multi-rate ad hoc wireless networks, Mobile Networks and Applications, v.11 n.2, p.253-266, April 2006
	Gábor Rétvári , József J. Bíró , Tibor Cinkler, On shortest path representation, IEEE/ACM Transactions on Networking (TON), v.15 n.6, p.1293-1306, December 2007
	Shieh-Shing Lin, A Parallel Algorithm for NMNF Problems with a Large Number of Capacity Constraints, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E90-A n.12, p.2884-2890, December 2007

INDEX TERMS

Primary Classification:
G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS
G.2.2 Graph Theory
Subjects: Network problems

Additional Classification:
G. Mathematics of Computing
G.1 NUMERICAL ANALYSIS
G.1.6 Optimization
Subjects: Linear programming

General Terms:
Algorithms, Theory

REVIEW

"Philip N. Klein : Reviewer"

A flurry of activity has recently occurred in algorithms for a variant of multicommodity flow called the maximum concurrent flow problem. Part of the interest is due to the fact that concurrent flow can be used in heuristics for finding separa more...

Collaborative Colleagues:

Tom Leighton: colleagues

Clifford Stein: colleagues

Fillia Makedon: colleagues

Éva Tardos: colleagues

Serge Plotkin: colleagues

Spyros Tragoudas: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player