Technical Note—On the Expected Performance of Branch-and-Bound Algorithms

J. K. Lenstra and A. H. G. Rinnooy Kan
Additional contact information
J. K. Lenstra: Mathematisch Centrum, Amsterdam, The Netherlands
A. H. G. Rinnooy Kan: Erasmus University, Rotterdam, The Netherlands

Operations Research, 1978, vol. 26, issue 2, 347-349

Abstract: For many combinatorial optimization problems, the use of enumerative solution methods exhibiting a superpolynomial worst-case behavior seems unavoidable. It is therefore of interest to investigate the expected behavior of such methods. Polynomial-bounded expected performance has been claimed by Bellmore and Malone for their traveling salesman algorithm. The purpose of this brief note is to point out some inadequacies of their proof.

Date: 1978
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.26.2.347 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:26:y:1978:i:2:p:347-349

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().