Acceleration Anomalies in Parallel Branch and Bound Algorithms

DOI Web Site Web Site

Bibliographic Information

Other Title
  • 並列型分枝限定法の異常加速効果
  • 並列型分枝限定法の異常加速効果--確率分布モデルによる解析
  • ヘイレツガタ ブンシゲン ジョウホウ ノ イジョウ カソク コウカ カクリツ
  • 確率分布モデルによる解析
  • Analysis based on a probability distribution model

Search this article

Description

Acceleration anomalies in paralell branch and bound algorithms may play a key role in solving NP-complete problems. As an analytical tool to deal with these phenomena, we propose a probability distribution model. From the computational results based on this model, we verify that the acceleration anomalies are accentuated by the appropriate handling of the various node selections, and if the applied lower bound function is of poor precision, this leads to a highly effective acceleration.<br>We apply these ideas to the task scheduling problem for parallel processing and confirm that the better solutions can be obtained with plural search strategies.

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top