Distributed algorithms for multicommodity flow problems via approximate steepest descent framework

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.

REFERENCES

• 1: {AA94} B. Awerbuch and Y. Azar. Local optimization of global objectives: Competitive distributed deadlock resolution and resource allocation. In Proc. 35th IEEE Symp. on Found. of Comp. Science, pages 240--249, 1994.
• 2: Yossi Azar , Joseph (Seffi) Naor , Raphael Rom, The competitiveness of on-line assignments, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.203-210, September 1992, Orlando, Florida, United States
• 3: Yair Bartal , John W. Byers , Danny Raz, Global Optimization Using Local Information with Applications to Flow Control, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.303, October 19-22, 1997
• 4: Eyal Even-Dar , Yishay Mansour, Fast convergence of selfish rerouting, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 5: Lisa K. Fleischer, Approximating Fractional Multicommodity Flow Independent of the Number of Commodities, SIAM Journal on Discrete Mathematics, v.13 n.4, p.505-520, Oct. 2000 to Nov. 2000 [doi>10.1137/S0895480199355754]
• 6: Simon Fischer , Harald Räcke , Berthold Vöcking, Fast convergence to Wardrop equilibria by adaptive sampling methods, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132608]
• 7: Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
• 8: Naveen Garg , Neal E. Young, On-Line End-to-End Congestion Control, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.303-312, November 16-19, 2002
• 9: Michael Luby , Noam Nisan, A parallel approximation algorithm for positive linear programming, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.448-457, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167211]
• 10: Serge A. Plotkin , David B. Shmoys , Éva Tardos, Fast approximation algorithms for fractional packing and covering problems, Mathematics of Operations Research, v.20 n.2, p.257-301, May 1995 [doi>10.1287/moor.20.2.257]
• 11: N. Young, Sequential and Parallel Algorithms for Mixed Packing and Covering, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.538, October 14-17, 2001