Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks

Full text

Pdf (910 KB)

Source

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

Montreal, Quebec, Canada

Pages: 487 - 496

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Baruch Awerbuch	Johns Hopkins University, Baltimore, MD and MIT Laboratory for Computer Science, Cambridge, MA
Tom Leighton	Department of Mathematics and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/195058.195238 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.

	AAMR93	William Aiello , Baruch Awerbuch , Bruce Maggs , Satish Rao, Approximate load balancing on dynamic and asynchronous networks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.632-641, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167250]
	AE83	Baruch Awerbuch and Shimon Even. A formal approach to a communication-network protocol; broadcast as a case study. Technical Report TR-459, Electrical Engineering Department, Technion-I.I.T., Haifa, December 1983.
	AG88	Eli Gafni , Yehuda Afek, End-to-end communication in unreliable networks, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.131-148, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62570]
	AG91	Yehuda Afek , Eli Gafni, Bootstrap network resynchronization (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.295-307, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112625]
	AGR92	Yehuda Afek , Eli Gafni , Adi Rosén, The slide mechanism with applications in dynamic networks, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.35-46, August 10-12, 1992, Vancouver, British Columbia, Canada [doi>10.1145/135419.135430]
	AL93	Baruch Awerbuch and Tom Leighton. A simple local-control approximation Mgorithm for multicommodity flow. In Proc. 3#rd IEEE Syrup. on Found. of Comp. Science, pages 459-46. IEEE, November 1993.
	AMS89	Baruch Awerbuch, Yishay Mansour, and Nit Shavit. End-to-end communication with polynomial overhead. In Proc. 30th IEEE Symp. on Found. of Comp. Science, pages 358-363, 1989.
	GT90	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]
	Kar74	A.V. Karzanov. Determining the maximal flow in a network by the method of preflows. Soviet Math. Dokl., 15:434-437, 1974.
	KARR90	P. Klein, A. Agrawal, R. Ravi, and S. Rao. Approximation through multicommodity flow. in Proc. 31st IEEE Symp. on Found. of Comp. Science, pages 726-727, 1990.
	KPP93	Anil Kamath, Omri Palmon, and Serge Plotkin. Simple and fast distributedmulticommondity flow algorithm. Unpublished manuscript, December 1993.
	LMP+91	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 [doi>10.1145/103418.103425]
	LR88	F.T. Leighton and Satish Rao. An approximate max-flow min-cut theorem for uniform multicommod ity flow problems with applications to approximation algorithms. In 29th Annual Symposium on Foundations of Computer Science, IEEE, pages 422-431, 1988.
	MS78	F.J. MacWilliams and N.:I.A. Sloane. The Theory of Error-Correcting Codes. North Holland Publishing Company, Amsterdam, 1978.
	Rab89	Michael O. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance, Journal of the ACM (JACM), v.36 n.2, p.335-348, April 1989 [doi>10.1145/62044.62050]
	Vai89	P.M. Vaidya. Speeding up linear programming using fast matrix multiplication, in Proc. 30th IEEE Syrup. on Found. of Comp. Science, pages 332-337, 1989.

CITED BY 32

	Allan Borodin , Jon Kleinberg , Prabhakar Raghavan , Madhu Sudan , David P. Williamson, Adversarial queueing theory, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.376-385, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Elliot Anshelevich , David Kempe , Jon Kleinberg, Stability of load balancing algorithms in dynamic adversarial systems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Allan Borodin , Jon Kleinberg , Prabhakar Raghavan , Madhu Sudan , David P. Williamson, Adversarial queuing theory, Journal of the ACM (JACM), v.48 n.1, p.13-38, Jan. 2001
	S. Muthukrishnan , Rajmohan Rajaraman, An adversarial model for distributed dynamic load balancing, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.47-54, June 28-July 02, 1998, Puerto Vallarta, Mexico
	David Karger , Serge Plotkin, Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.18-25, May 29-June 01, 1995, Las Vegas, Nevada, United States
	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
	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
	Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Log-space polynomial end-to-end communication, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.559-568, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Bhaskar Ghosh , F. T. Leighton , Bruce M. Maggs , S. Muthukrishnan , C. Greg Plaxton , R. Rajaraman , Andréa W. Richa , Robert E. Tarjan , David Zuckerman, Tight analyses of two local load balancing algorithms, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.548-558, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Chris Harrelson , Kirsten Hildrum , Satish Rao, A polynomial-time tree decomposition to minimize congestion, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	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
	Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999
	Matthew Andrews , Baruch Awerbuch , Antonio Fernández , Tom Leighton , Zhiyong Liu , Jon Kleinberg, Universal-stability results and performance bounds for greedy contention-resolution protocols, Journal of the ACM (JACM), v.48 n.1, p.39-69, Jan. 2001
	Baruch Awerbuch , Mohammad T. Hajiaghayi , Robert D. Kleinberg , Tom Leighton, Online client-server load balancing without global information, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Lujun Jia , Rajmohan Rajaraman , Christian Scheideler, On local algorithms for topology control and routing in ad hoc networks, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Mohammad T. Hajiaghayi , Robert D. Kleinberg , Tom Leighton , Harald Räcke, Oblivious routing on node-capacitated and directed graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Matthew Andrews , Antonio Fernández , Ashish Goel , Lisa Zhang, Source routing and scheduling in packet networks, Journal of the ACM (JACM), v.52 n.4, p.582-601, July 2005
	Kishore Kothapalli , Christian Scheideler, Information gathering in adversarial systems: lines and cycles, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Rajmohan Rajaraman, Topology control and routing in ad hoc networks: a survey, ACM SIGACT News, v.33 n.2, June 2002
	William Aiello , Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Adaptive packet routing for bursty adversarial traffic, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.359-368, May 24-26, 1998, Dallas, Texas, United States
	Marcel Busse , Thomas Haenselmann , Wolfgang Effelsberg, A comparison of lifetime-efficient forwarding strategies for wireless sensor networks, Proceedings of the 3rd ACM international workshop on Performance evaluation of wireless ad hoc, sensor and ubiquitous networks, October 06-06, 2006, Terromolinos, Spain
	Yuan Xue , Yi Cui , Klara Nahrstedt, Maximizing lifetime for data aggregation in wireless sensor networks, Mobile Networks and Applications, v.10 n.6, p.853-864, December 2005
	Matthew Andrews , Kyomin Jung , Alexander Stolyar, Stability of the max-weight routing and scheduling protocol in dynamic networks and at critical loads, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Mohammad Taghi Hajiaghayi , Robert D. Kleinberg , Harald Räcke , Tom Leighton, Oblivious routing on node-capacitated and directed graphs, ACM Transactions on Algorithms (TALG), v.3 n.4, p.51-es, November 2007
	Baruch Awerbuch , Rohit Khandekar, Distributed network monitoring and multicommodity flows: a primal-dual approach, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Baruch Awerbuch , Rohit Khandekar, Greedy distributed optimization of multi-commodity flows, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Kannan Rajah , Sanjay Ranka , Ye Xia, Scheduling bulk file transfers with start and end times, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.52 n.5, p.1105-1122, April, 2008
	Shoudong Zou , Ioanis Nikolaidis , Janelle Harms, Efficient aggregation using first hop selection in WSNs, International Journal of Sensor Networks, v.4 n.1/2, p.55-67, July 2008
	Abdallah Khreishah , Chih-Chun Wang , Ness B. Shroff, Capacity regions for multiple unicast flows using inter-session network coding, Proceedings of the 3rd international conference on Wireless internet, October 22-24, 2007, Austin, Texas
	Konstantinos Kalpakis , Shilang Tang, A combinatorial algorithm for the maximum lifetime data gathering with aggregation problem in sensor networks, Computer Communications, v.32 n.15, p.1655-1665, September, 2009
	Chun Hau Lau , Boon-Hee Soong , S. K. Bose, Path selection with preemption and re-routing control for multi-protocol label switching networks, Computer Communications, v.29 n.18, p.3718-3732, November, 2006
	Elona Erez , Meir Feder, Improving the multicommodity flow rates with network codes for two sources, IEEE Journal on Selected Areas in Communications, v.27 n.5, p.814-824, June 2009