  We give a lower bound on the iteration complexity of a natural class of
Lagrangean-relaxation algorithms for approximately solving packing/covering
linear programs. We show that, given an input with $m$ random 0/1-constraints
on $n$ variables, with high probability, any such algorithm requires
$\Omega(\rho \log(m)/\epsilon^2)$ iterations to compute a
$(1+\epsilon)$-approximate solution, where $\rho$ is the width of the input.
The bound is tight for a range of the parameters $(m,n,\rho,\epsilon)$.
  The algorithms in the class include Dantzig-Wolfe decomposition, Benders'
decomposition, Lagrangean relaxation as developed by Held and Karp [1971] for
lower-bounding TSP, and many others (e.g. by Plotkin, Shmoys, and Tardos [1988]
and Grigoriadis and Khachiyan [1996]). To prove the bound, we use a discrepancy
argument to show an analogous lower bound on the support size of
$(1+\epsilon)$-approximate mixed strategies for random two-player zero-sum
0/1-matrix games.
