On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms
<|reference_start|>On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms: 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.<|reference_end|>
@article{klein2002on,
    title={On the Number of Iterations for Dantzig-Wolfe Optimization and
  Packing-Covering Approximation Algorithms},
    author={Phil Klein, Neal E. Young},
    journal={LNCS 1610 (IPCO): 320-327 (1999); SIAM Journal on Computing
  44(4):1154-1172(2015)},
    year={2002},
    doi={10.1007/3-540-48777-8_24},
    archivePrefix={arXiv},
    eprint={cs/0205046},
    primaryClass={cs.DS cs.CC}
}