Skip to main content
Nearly Linear-Work Algorithms for Mixed Packing/Covering and Facility-Location Linear Programs
Published Web Locationhttps://arxiv.org/pdf/1407.3015.pdf
No data is associated with this publication.
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