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

2014/07/11 by Young, Neal E.
#49M29 #65K05 #90-08 #90C05 #Data Structures and Algorithms (cs.DS) #F.2.1 #FOS: Computer and information sciences #G.1.6

paper · doi:10.48550/arxiv.1407.3015

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+ε)-approximate solutions in time (and work) O^*(N/ε²), where N is the number of non-zeros in the constraint matrix. For facility location, N is the number of eligible client/facility pairs.

Related

• Nearly Linear-Time Packing and Covering LP Solvers
• Approximation schemes for covering and packing mixed-integer programs with a fixed number of constraints
• Online Mixed Packing and Covering
• Nearly-Linear Time LP Solvers and Rounding Algorithms for Scheduling Problems
• A parallel approximation algorithm for mixed packing and covering semidefinite programs