Beating simplex for fractional packing and covering linear programs

Neal Young

abstract:

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)