UC Riverside

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)/∈²) 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.