neal young / Klein15Number

  • Png/Klein99Number.png 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, the``width'' 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.
Download for personal and limited academic use only.