Randomized Selection on the Hypercube

✍ Scribed by Sanguthevar Rajasekaran

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 258 KB
• Volume: 37
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1996.0118

✦ Synopsis

In this paper, we present randomized algorithms for selection on the hypercube. We identify two variants of the hypercube, namely, the sequential model and the parallel model. In the sequential model, any node at any time can handle only communication along a single incident edge, whereas in the parallel model a node can communicate along all its incident edges at the same time. We specify three variations of the parallel model and present optimal randomized algorithms on all these three versions of parallel model. In particular, we show that selection on an input of size n can be performed on a p-node hypercube in time O((n/p) ؉ log p) with high probability, on any of the three versions of the parallel model. This result is important in view of a lower bound that implies that selection needs ⍀((n/p)log log p ؉ log p) time on a p-node sequential hypercube. We modify our selection algorithm to run on the sequential hypercube in which case it runs in an expected time nearly matching this lower bound. For the special case when n ‫؍‬ p, our selection algorithm runs in an optimal O(log n) time on the sequential hypercube. Our algorithms are very simple and are most likely to perform well in practice.