Nearly Linear-Time Packing and Covering LP Solvers

Understand

Packing and covering linear programs (PC-LPs) form an important class of linear programs (LPs) across computer science, operations research, and optimization.

• In 1993, Luby and Nisan constructed an iterative algorithm for approximately solving PC-LPs 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, all existing nearly linear-time algorithms for solving PC-LPs 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 $\tilde{O}(N \varepsilon^{-1})$ and covering LP solver that runs in time $\tilde{O}(N \varepsilon^{-1.5})$.