We study the complexity of approximately solving packing linear programs. In the Real
RAM model, it is known how to solve packing LPs with N non-zeros in time
Õ(N/ϵ). We investigate whether the ϵ dependence in the running time
can be improved.
Our first main result relates the difficulty of this problem to
hardness assumptions for solving dense linear equations. We show that, in the Real RAM
model,
unless linear equations in matrices n × n with condition number O(n^{10})
can be solved to ϵ accuracy faster than Õ(n^{2.01} log(1/ϵ)), no algorithm
(1−ϵ)-approximately
solves a O(n)×O(n) packing LPs (where N = O(n^{2}))
in time Õ(n^{2}ϵ^{−0.0003}). It would be surprising to solve linear
equations
in the Real RAM model this fast, as we currently cannot solve them faster than
Õ(n^{ω}), where
ω denotes the exponent in the running time for matrix multiplication in the Real RAM
model (and equivalently matrix inversion).
The current best bound on this exponent is roughly ω ≤ 2.372. Note, however, that a fast
solver for linear equations does not
directly imply faster matrix multiplication. But, our reduction shows that if fast and
accurate packing LP solvers exist, then either
linear equations can be solved much faster than matrix multiplication or the matrix
multiplication constant is very close to 2.
Instantiating the same reduction with different parameters, we show that unless linear
equations in matrices with condition number
O(n^{1.5}) can be solved to ϵ accuracy faster than Õ(n^{2.372}
log(1/ϵ)), no
algorithm (1 – ϵ)-approximately solves packing LPs in time
Õ(n^{2}ϵ^{−0.067}).
Thus smaller improvements in the exponent for ϵ in the running time of Packing LP
solvers also imply improvements in the current
state-of-the-art for solving linear equations.
Our second main result relates the difficulty of approximately solving packing
linear programs to hardness assumptions for solving sparse linear equations: In the Real
RAM model, unless well-conditioned sparse systems
of linear equations can be solved faster than Õ((no. non-zeros of matrix) ),
no algorithm (1 – ϵ)-approximately solves packing LPs with N non-zeros in time
Õ(Nϵ^{−0.165}). This
running time of Õ((no. non-zeros of matrix) )
is obtained by the classical Conjugate Gradient algorithm by a standard analysis. Our
reduction implies that if sufficiently good packing LP solvers exist, then this
long-standing best-known bound on the running time for solving well-conditioned systems
of linear equations is sub-optimal. While we prove results in the Real RAM model, our
condition number assumptions ensure that our results can be translated to fixed point
arithmetic with (log n)^{O(1)} bits per number.