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.