neal young / Klein15Number

SIAM Journal on Computing 44(4):11541172(2015); (IPCO'99)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 Lagrangianrelaxation 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 DantzigWolfe decomposition, Benders decomposition, the Lagrangianrelaxation method developed by Held and Karp [1971] for lowerbounding 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.