Skip to main content
Open Access Publications from the University of California

UC Riverside

UC Riverside Previously Published Works bannerUC Riverside

On the number of iterations for Dantzig-Wolfe optimization and packing-covering approximation algorithms

  • Author(s): Klein, P
  • Young, NE
  • et al.

Published Web Location

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.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
Current View