Abstract | ||
---|---|---|
In this paper, a parallel Optimal Best-First search Branch-and-Bound(B&B) algorithm(obs) is proposed and evaluated for MIN-based multiprocessor systems. The proposed algorithm decomposes a problem into a number of sub-problems and each sub-problem is processed on a small group of processors. A performance analysis is conducted to estimate the speed-up of the proposed parallel B&B algorithm. It considers both the computation and communication times to evaluate the realistic performance.Simulation data are given along with analysis results for model validation. It is shown that the proposed Optimal Best-First search B&B algorithm performs better than other reported schemes with its various advantageous features such as: less sub-problem evaluations, proper load balancing, and limited scope of remote communication through the network. |
Year | DOI | Venue |
---|---|---|
1999 | 10.1109/ICPP.1999.797395 | ICPP |
Keywords | DocType | ISBN |
performance analysis,proposed parallel b,analysis result,proposed optimal best-first search,communication time,remote communication,min-based multiprocessors,parallel optimal branch-and-bound algorithm,b algorithm,realistic performance,parallel optimal best-first search,proposed algorithm,broadcasting,concurrent computing,branch and bound,clustering algorithms,model validation,read only memory,branch and bound algorithm,algorithm design and analysis,parallel algorithms,load balancing,computer science,computational modeling,load balance,information technology | Conference | 0-7695-0350-0 |
Citations | PageRank | References |
1 | 0.59 | 6 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Myung K. Yang | 1 | 3 | 1.33 |
Chita R. Das | 2 | 258 | 28.49 |