Faster approximation schemes for fractional multicommodity flow problems

ABSTRACT

We present fully polynomial approximation schemes for concurrent multicommodity flow problems that run in time independent of the number of commodities k. We show that by modifying the algorithms by Garg & Könemann [5] and Fleischer [3] we can reduce their running time to a logarithmic dependence on k, and essentially match the running time of [3] for the maximum multicommodity flow problem.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: Yonatan Aumann , Yuval Rabani, An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm, SIAM Journal on Computing, v.27 n.1, p.291-301, Feb. 1998 [doi>10.1137/S0097539794285983]
• 3: 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]
• 4: Kevin D. Wayne , Lisa Fleischer, Faster approximation algorithms for generalized flow, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.981-982, January 17-19, 1999, Baltimore, Maryland, United States
• 5: 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
• 6: M. D. Grigoriadis and L. G. Khachiyan. Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM Journal on Optimization, 4:86-107, 1994.
• 7: Michael D. Grigoriadis , Leonid G. Khachiyan, Approximate minimum-cost multicommodity flows in O˜(&egr;-2KNM) time, Mathematical Programming: Series A and B, v.75 n.3, p.477-482, Dec. 16, 1996 [doi>10.1007/BF02592195]
• 8: 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 [doi>10.1145/225058.225073]
• 9: Philip Klein , Serge Plotkin , Clifford Stein , Eva Tardos, Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts, SIAM Journal on Computing, v.23 n.3, p.466-487, June 1994 [doi>10.1137/S0097539792241175]
• 10: Tom Leighton , Fillia Makedon , Serge Plotkin , Clifford Stein , Éva Tardos , Spyros Tragoudas, Fast approximation algorithms for multicommodity flow problems, Journal of Computer and System Sciences, v.50 n.2, p.228-243, April 1995
• 11: N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15:215-246, 1995.
• 12: 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]
• 13: 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
• 14: Farhad Shahrokhi , D. W. Matula, The maximum concurrent flow problem, Journal of the ACM (JACM), v.37 n.2, p.318-334, April 1990 [doi>10.1145/77600.77620]
• 15: David B. Shmoys, Cut problems and their application to divide-and-conquer, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 16: Neal E. Young, Randomized rounding without solving the linear program, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.170-178, January 22-24, 1995, San Francisco, California, United States