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 a 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-procesor distributed-memory Optically Connected Parallel Computer (OCPC). 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 with cost at most c*. When according for both computation and communication costs, our algorithm runs in time O(n/p+h(max{p,log nlog p})2) for general values of n, and can be made to run in time O((n/p+hlog4p)log log p) for n polynomial in p. For large ranges of the relevant parameters, our algorithm is provably optimal and improves asymptotically upon the well-known randomized strategy by Karp and Zhang.

### Deterministic branch-and-bound on distributed memory machines.

#### Abstract

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 a 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-procesor distributed-memory Optically Connected Parallel Computer (OCPC). 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 with cost at most c*. When according for both computation and communication costs, our algorithm runs in time O(n/p+h(max{p,log nlog p})2) for general values of n, and can be made to run in time O((n/p+hlog4p)log log p) for n polynomial in p. For large ranges of the relevant parameters, our algorithm is provably optimal and improves asymptotically upon the well-known randomized strategy by Karp and Zhang.
##### Scheda breve Scheda completa Scheda completa (DC) 1999
File in questo prodotto:
Non ci sono file associati a questo prodotto.
##### Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11577/2463369`
##### Citazioni
• ND
• ND
• ND