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 Omega(rho log(m)/epsilon(2)) iterations to compute a (1 + epsilon)-approximate solution, where. 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, 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 + epsilon)-approximate mixed strategies for random two-player zero-sum 0/1-matrix games.