On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms

Abstract

We give a lower bound on the iteration complexity of a natural class of Lagrangean-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 $\rho$ 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, Lagrangean relaxation as developed by Held and Karp [1971] for lower-bounding TSP, and many others (e.g. by Plotkin, Shmoys, and Tardos [1988] and Grigoriadis and Khachiyan [1996]). 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.

References in corpus (3)

• Sequential and Parallel Algorithms for Mixed Packing and Covering
• A Nearly Linear-Time PTAS for Explicit Fractional Packing and Covering Linear Programs
• On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms

Cited by in corpus (9)

• Sequential and Parallel Algorithms for Mixed Packing and Covering
• A Nearly Linear-Time PTAS for Explicit Fractional Packing and Covering Linear Programs
• On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms
• Tight Bounds for Approximate Carathéodory and Beyond
• Approximate Convex Optimization by Online Game Playing
• On-Line End-to-End Congestion Control
• Faster Approximation Schemes for Fractional Multicommodity Flow Problems via Dynamic Graph Algorithms
• On the Convergence of Step Decay Step-Size for Stochastic Optimization
• Adversarial Online Learning with noise