An upper bound for the speedup of parallel best-bound branch-and-bound algorithms |
| |
| Authors: | Michael J. Quinn Narsingh Deo |
| |
| Affiliation: | (1) Department of Computer Science, University of New Hampshire, 03824 Durham, New Hampshire, USA;(2) Computer Science Department, Washington State University, 99164 Pullman, Washington, USA |
| |
| Abstract: | This paper derives an upper bound for the speedup obtainable by any parallel branch-and-bound algorithm using the best-bound search strategy. We confirm that parallel branch-and-bound can achieve nearly linear, or even super-linear, speedup under the appropriate conditions.This work was supported by U.S. Army Research Office grant DAAG29-82-K-0107. |
| |
| Keywords: | F.2.2 Nonnumerical Algorithms and Problems G.2.2 Graph Theory |
| 本文献已被 SpringerLink 等数据库收录！ |
|
