Solving fractional packing problems in Oast(1/ε) iterations

ABSTRACT

We adapt a method proposed by Nesterov [16] to design an algorithm that computes ε-optimal solutions to fractional packing problems by solving O^*(ε^-1 √Kn) separable convex quadratic programs, where K is the maximum number of non-zeros per row and n is the number of variables. We also show that the quadratic program can be approximated to any degree of accuracy by an appropriately defined piecewise-linear program. For the special case of the maximum concurrent flow problem on a graph G =(V,E) with rational capacities and demands we obtain an algorithm that computes an Ε-optimal flow by solving O*(ε^-1 K^3/2|E| √|V| (log 1/ε+ LU + LD)) shortest path problems, where K is the number of commodities, and LU, LD are, respectively, the number of bits needed to store the capacities and demands. We also show that the complexity of computing a maximum multicommodity flow is O^*(1/εlog2(1/ε)). In contrast, previous algorithms required Ω(ε^-2) iterations.

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: D. Bienstock. Potential Function Methods for Approximately Solving Linear Programming Problems, Theory and Practice, Kluwer, Boston. 2002. An early version downloadable from www. core. ucl. ac. be.
• 3: D. Bienstock and O. Raskina. Asymptotic analysis of the flow deviation method for the maximum concurrent flow problem. Math. Prog. 91:379--492, 2002.
• 4: 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]
• 5: M. Frank and P. Wolfe. An algorithm for quadratic programming. Naval Res. Log. Quart. 3:149--154, 1956.
• 6: L. Fratta, M. Gerla and L. Kleinrock. The flow deviation method: an approach to store-and-forward communication network design. Networks 3:97--133, 1971.
• 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: M. D. Grigoriadis and L. G. Khachiyan. Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM J. Optim., 4:86--107, 1994.
• 9: M. D. Grigoriadis and L. G. Khachiyan. An exponential-function reduction method for block-angular convex programs. Networks 26:59--68, 1995.
• 10: 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]
• 11: M. Minoux. A polynomial algorithm for minimum quadratic cost flows. European J. Oper. Res. 18:377--387, 1984.
• 12: P. Klein, S. Plotkin, C. Stein and E. Tardos. Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing with applications to multicommodity flows. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC), 18--25, 1995.
• 13: Philip N. Klein , Neal E. Young, On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms, Proceedings of the 7th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.320-327, June 09-11, 1999
• 14: Tom Leighton , Clifford Stein , Fillia Makedon , Éva Tardos , Serge Plotkin , Spyros Tragoudas, Fast approximation algorithms for multicommodity flow problems, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.101-111, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103425]
• 15: Arkadi Nemirovski, Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems, SIAM Journal on Optimization, v.15 n.1, p.229-251, 2005 [doi>10.1137/S1052623403425629]
• 16: Y. Nesterov. Smooth minimization of non-smooth functions. CORE Discussion Paper, CORE, UCL, Belgium. 2003.
• 17: 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]
• 18: 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]
• 19: 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
• 20: 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]
• 21: J. Villavicencio and M. D. Grigoriadis. Approximate Lagrangian decomposition using a modified Karmarkar logarithmic potential. In Network Optimization (Pardalos and Hager, eds. ) Lecture Notes in Economics and Mathematical Systems 450 Springer-Verlag, Berlin, 471--485, 1995.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms