Back to Search
Start Over
ON THE NUMBER OF ITERATIONS FOR DANTZIG-WOLFE OPTIMIZATION AND PACKING-COVERING APPROXIMATION ALGORITHMS.
- Source :
-
SIAM Journal on Computing . 2015, Vol. 44 Issue 4, p1154-1172. 19p. - Publication Year :
- 2015
-
Abstract
- We give a lower bound on the iteration complexity of a natural class of Lagrangianrelaxation 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 Ω(ρ log(m)/ϵ2) iterations to compute a (1 + ϵ)-approximate solution, where ρ is the width of the input. The bound is tight for a range of the parameters (m, n, ρ, ϵ). The algorithms in the class include Dantzig-Wolfe decomposition, Benders' decomposition, Lagrangian relaxation as developed by Held and Karp for lower-bounding TSP, and many others (e.g., those by Plotkin, Shmoys, and Tardos and Grigoriadis and Khachiyan). To prove the bound, we use a discrepancy argument to show an analogous lower bound on the support size of (1 + ϵ)-approximate mixed strategies for random two-player zero-sum 0/1-matrix games. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 44
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 109265802
- Full Text :
- https://doi.org/10.1137/12087222X