Beating simplex for fractional packing and covering linear programs
We describe an approximation algorithm for packing and covering linear
programs (linear programs with non-negative 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+epsilon of the optimal
cost in time O( n + (r+c)log(n)/epsilon^2 ).
For dense problems (with r,c=O(sqrt(n))) this time is
O(n +sqrt(n)log(n)/epsilon^2) --- linear even as epsilon tends to zero. In
comparison, previous Lagrangian-relaxation algorithms generally take
at least Omega(n log(n)/epsilon^2) time, while (for small epsilon) the
Simplex algorithm typically takes at least Omega(n min(r,c)) time.
This extends a previous algorithm by Grigoriadis and Khachiyan for
approximately solving 2-player zero-sum games in sub-linear time.
(Joint work with Christos Koufogiannakis)