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

Jan Karel Lenstra | Zendy; A. H. G. Rinnooy Kan | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

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

Author(s) -

Jan Karel Lenstra,

A. H. G. Rinnooy Kan

Publication year - 1978

Publication title -

operations research

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 3.797

H-Index - 140

eISSN - 1526-5463

pISSN - 0030-364X

DOI - 10.1287/opre.26.2.347

Subject(s) - travelling salesman problem , branch and bound , bounded function , point (geometry) , combinatorial optimization , mathematical optimization , mathematics , computer science , algorithm , mathematical analysis , geometry

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research