Name
Title | ||
|---|---|---|
Analytical Modeling of a Parallel Branch-and-Bound Algorithm on MIN-Based Multiprocessors |
Abstract | ||
|---|---|---|
The authors propose a parallel decomposite, best-first' search branch-and bound algorithm for MIN-based multiprocessors. They start with a new probabilistic model to estimate the number of evaluated nodes for a serial algorithm. The proposed algorithm initially decomposes a problem into several subproblems. Each processor executes the serial best-first search to find a local feasible solution. The local solutions are broadcast through the network to compute the final solution. The speed-up analysis considers both the computation and communication overheads. It is seen that the parallel decomposite best-first search algorithm performs better than other reported schemes when communication overhead is taken into consideration. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1109/IPPS.1992.223037 | Beverly Hills, CA |
Keywords | Field | DocType |
serial algorithm,local solution,final solution,parallel decomposite best-first search,serial best-first search,communication overhead,parallel decomposite,proposed algorithm,analytical modeling,parallel branch-and-bound algorithm,min-based multiprocessors,branch-and bound algorithm,local feasible solution,linear programming,search algorithm,algorithm design and analysis,best first search,computer networks,broadcasting,branch and bound algorithm,probabilistic model,computer architecture,parallel algorithms | Branch and bound,Search algorithm,Min-conflicts algorithm,Parallel algorithm,Computer science,Parallel computing,Beam search,Local search (optimization),Binary search algorithm,Best-first search | Conference |
ISBN | Citations | PageRank |
0-8186-2672-0 | 0 | 0.34 |
References | Authors | |
5 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Myung K. Yang | 1 | 3 | 1.33 |
| Chita R. Das | 2 | 258 | 28.49 |