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 Lagrangian-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 Ω(ρ log(m)/ε²) 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.