How to Cope with Anomalies in Parallel Approximate Branch-and-Bound Algorithms
Abstract
Abstract: A genera! technique for solving a wide variety of search problems is the branch-and-bound (B&B) algorithm. We have adapted and extended B&B algorithms for parallel processing. Anomalies owing to parallelism may occur.-In this paper sufficient conditions to guarantee that parallelism will not degrade the performance are presented. Necessary condi-tions for allowi & parallelism to have a speedup greater than the number of processors are also shown. Anomalies are found to occur infrequently when optima! solutions are sought; how-ever, they are frequent in- approximate B&B algorithms. Theoretical analysis and simulations show that a best-first search is robust for parallel processing. 1.
Cite
Text
Li and Wah. "How to Cope with Anomalies in Parallel Approximate Branch-and-Bound Algorithms." AAAI Conference on Artificial Intelligence, 1984.Markdown
[Li and Wah. "How to Cope with Anomalies in Parallel Approximate Branch-and-Bound Algorithms." AAAI Conference on Artificial Intelligence, 1984.](https://mlanthology.org/aaai/1984/li1984aaai-cope/)BibTeX
@inproceedings{li1984aaai-cope,
title = {{How to Cope with Anomalies in Parallel Approximate Branch-and-Bound Algorithms}},
author = {Li, Guo-Jie and Wah, Benjamin W.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {1984},
pages = {212-215},
url = {https://mlanthology.org/aaai/1984/li1984aaai-cope/}
}