Please use this identifier to cite or link to this item:
|Title:||Branch and bound on the network model||Authors:||Jain, S.||Keywords:||Branch and bound
|Issue Date:||2001||Citation:||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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.