• SIAM Journal on Computing 44(4):1154-1172(2015); (IPCO'99)

  With Philip Klein
  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.

  • more...
  •   full text
    
  •   bibtex
    
  •   google scholar
    
  •   doi
    

© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.