Parallel branch and bound and anomalies
January 1989
Research Paper
| Related Files |
|---|
View PDF Version
(eur-few-cs-89-01.pdf, 0.1MB) |
In this paper we present a classification of parallel branch and bound algorithms and investigate the anomalies which can occur during the execution of such algorithms. We develop sufficient conditions to prevent deceleration anomalies from degrading the performance. Such conditions were already known for some synchronous cases. It turns out that these conditions can be generalized to arbitrary cases. Finally we develop necessary conditions for acceleration anomalies to improve upon the performance.
Keywords
Automatically Extracted Terms
- subproblem
- algorithm
- branch
- process
- solution
- heuristic
- heuristic value
- sequential algorithm
- anomaly
- value
- execution
- heuristic function
- function
- sequential
- knowledge
- problem
- problem instance
- dominance
- dominance test
- elimination rule
