Performance of parallel branch-and-bound algorithms

1 October 1985

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers

Vol. C-34 (10) , 962-964
https://doi.org/10.1109/TC.1985.6312201

Abstract

Consideration is given to the performance of parallel best-bound-first branch-and-bound algorithms in which several nodes with least lower bounds are expanded simultaneously. It is well known that anomalies may occur in the execution of a parallel branch-and-bound algorithm. The authors show the conditions under which anomalies are guaranteed not to occur when the number of processors is doubled, or not even doubled.

Keywords

PROGRAM PROCESSORS
PARALLEL PROCESSING
APPROXIMATION ALGORITHMS
EDUCATIONAL INSTITUTIONS
COMPUTERS
GEOMETRY
ALGORITHM DESIGN AND ANALYSIS