**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)