An upper bound for the speedup of parallel best-bound branch-and-bound algorithms
type: Item
instance of: scholarly article
title: An upper bound for the speedup of parallel best-bound branch-and-bound algorithms
zbMATH Open document ID: 0587.90094
DOI: 10.1007/BF01939360
author: Michael J. Quinn
author: Narsingh Deo
published in: BIT
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 3943580
zbMATH Keywords: traveling salesman
zbMATH Keywords: upper bound
zbMATH Keywords: parallel branch-and-bound algorithm
MaRDI profile type: Publication
cites work: Integer Programming Algorithms: A Framework and State-of-the-Art Survey
cites work: The traveling-salesman problem and minimum spanning trees: Part II
cites work: Theoretical comparisons of search strategies in branch-and-bound algorithms
cites work: Anomalies in parallel branch-and-bound algorithms
cites work: An Algorithm for the Traveling Salesman Problem
cites work: Q3856120
cites work: Tree-search algorithms for quadratic assignment problems
cites work: Solving Resource-Constrained Network Problems by Implicit Enumeration—Nonpreemptive Case
cites work: Solving Resource-Constrained Network Problems by Implicit Enumeration—Preemptive Case
description: scientific article; zbMATH DE number 3943580