Stateless distributed algorithms for near optimal maximum multicommodity flows

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Stateless distributed algorithms for near optimal maximum multicommodity flows

Full text

Pdf (108 KB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing table of contents

Toronto, Canada

SESSION: B3-1 table of contents

Pages 440-440

Year of Publication: 2008

ISBN:978-1-59593-989-0

Authors

Baruch Awerbuch	Johns Hopkins University, Baltimore, MD, USA
Rohit Khandekar	IBM T.J. Watson Research Center, Yorktown Heights, NY, USA

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 62, Citation Count: 0

Additional Information:

abstract references 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/1400751.1400835 What is a DOI?

ABSTRACT

We design a stateless and distributed solution to the problem of maximum multicommodity flows--route the maximum amount of flow between given source-sink pairs, possibly split along several paths, subject to edge-capacity constraints. Our main contribution is in extending the work of [1,2] to the case where the flow can be routed along possibly exponentially many different paths. Our algorithm, starting from an arbitrary feasible flow, always maintains a feasible flow, and reaches a 1 + ε approximation of maximum benefit value in Õ(n²) rounds.

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	B. Awerbuch and R. Khandekar. Stateless near optimal flow control with poly-logarithmic convergence. In LATIN, 2008.
	2	Baruch Awerbuch , Rohit Khandekar, Stateless distributed gradient descent for positive linear programs, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374476]