Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks
Baruch Awerbuch, Tom Leighton · 1994
In this paper, we describe a very simple boundedqueuesize local-control algorithm for routing multicommodity flows in a dynamically-changing distributed network. The algorithm is based on the edge-balancing approach described in [AL93], but has the added benefits of: 1. a much improved running time, and 2. working even in networks where edge capacities can vary in an unpredictable and unknown fashion. In fact, the sequential running time of the algorithm is now comparable to (and, in some cases, better than) the time of the best previously known approximation algorithms for the multi-commodity flow problem in a fixed network [LMP + 91]. The fact that the new algorithm works well in dynamically changing networks means that problems such as end-to-end communication and load balancing [AMS89, AGR92, AAMR93] can now be solved in Johns Hopkins University, Baltimore, MD 21218-2694, and MIT Laboratory for Computer Science, Cambridge MA 02139. Email: [email protected]. Supported by...