## neal young / Klein15Number

• This paper gives a lower bound on the complexity of $$(1 \pm \epsilon)$$-approximately solving a packing or covering problem using a certain class of Lagrangian-relaxation algorithms: any such algorithm, given a problem formed by a random {0,1}-matrix, requires (with high probability) a number of iterations proportional to $$(\rho \epsilon)^2\log m$$. (Here $$\rho$$ is a technical parameter, thewidth'' of the problem instance.)

The class of algorithms in question includes Dantzig-Wolfe decomposition, Benders decomposition, the Lagrangian-relaxation method developed by Held and Karp [1971] for lower-bounding TSP, and algorithms recently studied by many authors (including Serge Plotkin, David Shmoys, and Eva Tardos [1988]; Mike Grigoriadis and L.G. Khachiyan [1996]; Michael Luby and Noam Nisan [1993]; Naveen Garg and Jochen Konemann [1998]; and Lisa Fleischer [1999]). The lower bound matches the known upper bounds within a constant factor. The lower bound is useful because, in practice, the dependence on $$\epsilon$$ limits the applicability of these algorithms. The lower bound provides some insight into what is necessary to surmount this dependence.
Journal version of [1999]. Published online Aug. 2015.

© Copyrights are reserved by the publishers.