Beating Simplex for Fractional Packing and Covering Linear Programs

We give an approximation algorithm for packing and covering linear programs (linear programs with nonnegative coefficients). Given a constraint matrix with n non-zeros, r rows, and c columns, the algorithm (with high probability) computes feasible primal and dual solutions whose costs are within a factor of 1 + \varepsilon of OPT (the optimal cost) in time {\rm O}(n + (r + c)\log (n)/\varepsilon ^2 ). For dense problems (with r,c = {\rm O}(\sqrt n )) the time is {\rm O}(n + \sqrt n \log (n)/\varepsilon ^2 ) - linear even as \varepsilon\to 0. In comparison, previous Lagrangian-relaxation algorithms generally take at least \Omega (n\log (n)/\varepsilon ^2 ) time, while (for small \varepsilon) the Simplex algorithm typically takes at least \Omega (n\min (r,c)) time.