An upper bound for the speedup of parallel best-bound branch-and-bound algorithms

descriptionPublicationkeyboard_double_arrow_right Article 01 Mar 1986 English Publisher:Springer Science and Business Media LLCJournal:BIT, volume 26, pages 35-43 (issn: 0006-3835, eissn: 1572-9125,

Copyright policy )

Authors: Michael J. Quinn; Narsingh Deo;

doi: 10.1007/bf01939360

An upper bound for the speedup of parallel best-bound branch-and-bound algorithms

- Summary
- Subjects
- Metrics

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.

Related Organizations

University of New Hampshire
United States
Washington State University
United States

Keywords

parallel branch-and-bound algorithm, Numerical mathematical programming methods, Analysis of algorithms and problem complexity, traveling salesman, upper bound, Integer programming, Programming involving graphs or networks

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	12
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average