Distributed algorithms for multicommodity flow problems via approximate steepest descent framework
Authors:
Open Access
- 26 December 2012
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 9 (1) , 1-14
Abstract
We consider solutions for distributed multicommodity flow problems, which are solved by multiple agents operating in a cooperative but uncoordinated manner. We show first distributed solutions that allow (1 + ϵ) approximation and whose convergence time is essentially linear in the maximal path length, and is independent of the number of commodities and the size of the graph. Our algorithms use a very natural approximate steepest descent framework, combined with a blocking flow technique to speed up the convergence in distributed and parallel environment. Previously known solutions that achieved comparable convergence time and approximation ratio required exponential computational and space overhead per agent.Keywords
Funding Information
- Division of Computing and Communication Foundations (CCF-0515080, ANIR-0240551, and CCR-0311795)
- National Science Foundation (CCF-0515080, ANIR-0240551, and CCR-0311795)
This publication has 11 references indexed in Scilit:
- Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms2010
- Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing ProblemsSIAM Journal on Computing, 2007
- Fast convergence to Wardrop equilibria by adaptive sampling methods2006
- Approximating Fractional Packings and Coverings in O(1/epsilon) IterationsSIAM Journal on Computing, 2006
- Throughput-competitive on-line routing2002
- Local optimization of global objectives: competitive distributed deadlock resolution and resource allocation2002
- Approximating Fractional Multicommodity Flow Independent of the Number of CommoditiesSIAM Journal on Discrete Mathematics, 2000
- Approximate minimum-cost multicommodity flows in $\tilde O$ (ɛ −2 KNM) timetimeMathematical Programming, 1996
- Fast Approximation Algorithms for Fractional Packing and Covering ProblemsMathematics of Operations Research, 1995
- A parallel approximation algorithm for positive linear programming1993