Fast deterministic parallel branch-and-bound

The branch-and-bound problem involves determining the minimum cost leaf in a cost-labelled tree, subject to the constraint that only the root is known initially and that children are revealed only by visiting their parent. We present the first efficient deterministic algoritlim to solve the branchand-bound problem for a tree T of constant degree on a p-processor parallel machine. Let c* be the cost of the minimum-cost leaf in T, and let n and h be the number of nodes and the height, respectively, of the subtree T* ≤ T of nodes of cost less than or equal to c. Our algorithm runs in O (n/p + h log²(np)) time on an EREW-PRAM. Moreover, the running time faithfully reflects both communication and computation costs, unlike most of the previous results where the cost of local computation is ignored. For large ranges of the parameters, our algorithm matches the optimal performance of existing randomized strategies. The algorithm can be ported to any architecture for which an efficient implementation of Parallel Priority Queues [PP91] is available.