neal young / Koufogiannakis13Nearly

Algorithmica 70(4):648674(2014); FOCS'07We give an approximation algorithm for packing and covering linear programs (linear programs with nonnegative coefficients). Given a constraint matrix with $N$ nonzeros, $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((r+c)\log(N)/\epsilon^2 + N)$.Journal version of [2007].
© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.