Skip to main content
eScholarship
Open Access Publications from the University of California

UC Riverside

UC Riverside Previously Published Works bannerUC Riverside

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

  • Author(s): Koufogiannakis, C
  • Young, NE
  • et al.
Abstract

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

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
Current View