We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
ON THE EFFECTIVENESS OF SYNCHRONOUS PARALLEL BRANCH-AND-BOUND ALGORITHMS.
- Authors
CORRÊA, RICARDO; FERREIRA, AFONSO
- Abstract
We theoretically compare the efficiency of two versions, sequential and parallel (synchronous), of the method called branch-and-bound used for searching for an optimal solution in the scope of combinatorial optimization. The sequential version consists of successive decompositions of the original problem in smaller disjoint subproblems and its parallel version consists of a high level parallelization that assumes a shared memory model of parallel computation. Its principle consists of decomposing several subproblems in parallel at each iteration in a synchronous way, and its efficiency is usually defined with respect to its sequential counterpart. In this paper, we redefine the notion of efficiency in such a way that the usefulness of the work done by each processor will be taken into account. The knapsack problem is used as an application and some simulation results are presented to validate and illustrate the use of the new efficiency measures.
- Publication
Parallel Processing Letters, 1995, Vol 5, Issue 3, p375
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S0129626495000357