TY - CHAP
T1 - Deterministic branch-and-bound on distributed memory machines
AU - Herley, Kieran T.
AU - Pietracaprina, Andrea
AU - Pucci, Geppino
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1999.
PY - 1999
Y1 - 1999
N2 - The branch-and-bound problem involves determining the leaf of minimum cost in a cost-labelled, heap-ordered tree, subject to the constraint that only the root is known initially and that the children of each node are revealed only by visiting their parent. We present the first efficient deterministic algorithm to solve the branch-and-bound problem for a tree T of constant degree on a p-processor Distributed-Memory Machine. Let c* be the cost of the minimumcost leaf in T, and let n and h be the number of nodes and the height, respectively, of the subtree T* ⊆ T of nodes whose cost is at most c*. When accounting for both computation and communication costs, our algorithm runs in time O (n/p + h(max{p, lognlogp})2) for general values of n, and can be made to run in time O ((n/p + hlog4 p)log logp) for n polynomial in p. For large ranges of the relevant parameters, our algorithm is provably optimal or outperforms the well-known randomized strategy by Karp and Zhang.
AB - The branch-and-bound problem involves determining the leaf of minimum cost in a cost-labelled, heap-ordered tree, subject to the constraint that only the root is known initially and that the children of each node are revealed only by visiting their parent. We present the first efficient deterministic algorithm to solve the branch-and-bound problem for a tree T of constant degree on a p-processor Distributed-Memory Machine. Let c* be the cost of the minimumcost leaf in T, and let n and h be the number of nodes and the height, respectively, of the subtree T* ⊆ T of nodes whose cost is at most c*. When accounting for both computation and communication costs, our algorithm runs in time O (n/p + h(max{p, lognlogp})2) for general values of n, and can be made to run in time O ((n/p + hlog4 p)log logp) for n polynomial in p. For large ranges of the relevant parameters, our algorithm is provably optimal or outperforms the well-known randomized strategy by Karp and Zhang.
UR - https://www.scopus.com/pages/publications/84957659621
U2 - 10.1007/BFb0097994
DO - 10.1007/BFb0097994
M3 - Chapter
AN - SCOPUS:84957659621
SN - 3540658319
SN - 9783540658313
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 1085
EP - 1094
BT - Parallel and Distributed Processing - 11 th IPPS/SPDP 1999 Workshops Held in Conjunction with the 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing, Proceedings
A2 - Rolim, José
PB - Springer Verlag
T2 - 13th International Parallel Processing Symposium, IPPS 1999 Held in Conjunction with the 10th Symposium on Parallel and Distributed Processing, SPDP 1999
Y2 - 12 April 1999 through 16 April 1999
ER -