Nearly Linear-Time Packing and Covering LP Solvers


Packing and covering linear programs (PC-LP s) form an important class of linear programs (LPs) across computer science, operations research, and optimization. Luby and Nisan (STOC 1993) constructed an iterative algorithm for approximately solving PC-LP s in nearly linear time, where the time complexity scales nearly linearly in $N$, the number of nonzero entries of the matrix, and polynomially in $\varepsilon $, the (multiplicative) approximation error. Unfortunately, existing nearly linear-time algorithms for solving PC-LP s require time at least proportional to $\varepsilon ^{-2}$. In this paper, we break this longstanding barrier by designing a packing solver that runs in time $\widetilde{O}(N \varepsilon ^{-1})$ and covering LP solver that runs in time $\widetilde{O}(N \varepsilon ^{-1.5})$. Our packing solver can be extended to run in time $\widetilde{O}(N \varepsilon ^{-1})$O for a class of well-behaved covering programs. In a follow-up work, Wang et al. (ICALP 2016) showed that all covering LPs can be converted into well-behaved ones by a reduction that blows up the problem size only logarithmically.

Mathematical Programming: Series A and B