  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})$. Our packing solver can be
extended to run in time $\tilde{O}(N \varepsilon^{-1})$ for a class of
well-behaved covering programs. In a follow-up work, Wang et al. showed that
all covering LPs can be converted into well-behaved ones by a reduction that
blows up the problem size only logarithmically.
  At high level, these two algorithms can be described as linear couplings of
several first-order descent steps. This is an application of our linear
coupling technique to problems that are not amenable to blackbox applications
known iterative algorithms in convex optimization.
