A Nearly Linear-Time PTAS for Explicit Fractional Packing and Covering Linear Programs

摘要

We give an approximation algorithm for fractional 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 + ε of OPT (the optimal cost) in time O((r + c) log(n)/ε~2 + n).