Please use this identifier to cite or link to this item: https://doi.org/10.1016/S0304-3975(99)00158-9
Title: Branch and bound on the network model
Authors: Jain, S. 
Keywords: Branch and bound
Parallel algorithms
Issue Date: 2001
Source: Jain, S. (2001). Branch and bound on the network model. Theoretical Computer Science 255 (1-2) : 107-123. ScholarBank@NUS Repository. https://doi.org/10.1016/S0304-3975(99)00158-9
Abstract: Karp and Zhang developed a general randomized parallel algorithm for solving branch and bound problems. They showed that with high probability their algorithm attained optimal speedup within a constant factor (for p≤n/(logn) c, where p is the number of processors, n is the "size" of the problem, and c is a constant). Ranade later simplified the analysis and obtained a better processor bound. Karp and Zhang's algorithm works on models of computation where communication cost is constant. The present paper considers the Branch and Bound problem on networks where the communication cost is high. Suppose sending a message in a p processor network takes G = O(logp) time and node expansion (defined below) takes unit time (other operations being free). Then a simple randomized algorithm is presented which is, asymptotically, nearly optimal for p = O(2 logc n), where c is any constant <1/3 and n is the number of nodes in the input tree with cost no greater than the cost of the optimal leaf in the tree. © 2001 Elsevier Science B.V. All rights reserved.
Source Title: Theoretical Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/39422
ISSN: 03043975
DOI: 10.1016/S0304-3975(99)00158-9
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

1
checked on Dec 5, 2017

WEB OF SCIENCETM
Citations

1
checked on Dec 5, 2017

Page view(s)

46
checked on Dec 11, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.