Nearly Linear-Work Algorithms for Mixed Packing/Covering and Facility-Location Linear Programs
Skip to main content
eScholarship
Open Access Publications from the University of California

UC Riverside

UC Riverside Previously Published Works bannerUC Riverside

Nearly Linear-Work Algorithms for Mixed Packing/Covering and Facility-Location Linear Programs

  • Author(s): Young, Neal E
  • et al.

Published Web Location

https://arxiv.org/pdf/1407.3015.pdf
No data is associated with this publication.
Abstract

We describe the first nearly linear-time approximation algorithms for explicitly given mixed packing/covering linear programs, and for (non-metric) fractional facility location. We also describe the first parallel algorithms requiring only near-linear total work and finishing in polylog time. The algorithms compute $(1+\epsilon)$-approximate solutions in time (and work) $O^*(N/\epsilon^2)$, where $N$ is the number of non-zeros in the constraint matrix. For facility location, $N$ is the number of eligible client/facility pairs.

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.

Item not freely available? Link broken?
Report a problem accessing this item