Fast approximations to solve packing/covering LPs and constant-sum games via multiplicative-weights technique

Fast approximations to solve packing/covering LPs and constant-sum games via multiplicative-weights technique

Ajay Shankar Bidyarthy∗ Rajiv Raman† Dilys Thomas†

June 1, 2012

The multiplicative weights algorithm is a well-known technique for approximately solving packing/covering linear programs. The technique originated in the 1940s in the context of solving constant-sum games. There has been considerable recent research building on this work, develop-ing fast and approximate solutions to packing/covering linear as well as semi-definite programs.
We have implemented several variants of this technique and evaluated these algorithms experimentally. In particular, we evaluated the non-uniform increment technique of Garg and K ̈nemann o [1], as well as recent extensions by Koufogiannakis and Young [2]. The performance of our implementation compare well with the best linear programming solvers. For example, the figure on the
left shows our algorithms run much faster for moderately small approximation factors and largeinstances (5000 × 5000 dense real matrices), compared to Sedumi [3] (a well-known LP and SDP solver), while the figure on the right shows that Sedumi can converge faster ( < 0.02) than the classic Grigoriadis-Khachiyan fictitious play.

These algorithms are a building-block for solving large-scale combinatorial optimization problems approximately. Our algorithms have been implemented in MATLAB and have been tested on multiple modern 2-core machines.

References
[1] Naveen Garg and Jochen K ̈nemann. Faster and simpler algorithms for multicommodity flow o and other fractional packing problems. SIAM J. Comput., 37(2):630–652, 2007.
[2] Christos Koufogiannakis and Neal E. Young. Beating simplex for fractional packing and covering linear programs. CoRR, abs/0801.1987, 2008. (earlier published in FOCS 2007).
[3] Jos. F. Strum. SeDuMi ver. 1.3, http://sedumi.ie.lehigh.edu/.

∗ Indian Institute of Technology, Guwahati, India. E-mail: b.ajay@iitg.ac.in
† TCS Innovation labs, TRDDC, Pune, India. E-mail: rajiv.raman@tcs.com,dilys@cs.stanford.com