Approximate and Exact Deterministic Parallel Selection

Abstract The selection problem of size n is, given a set of n elements drawn from an ordered universe and an integer r with 1< r ≤ n, to identify the r th smallest element in the set. We study approximate and exact selection on deterministic concurrent-read concurrent-write parallel RAMs, where approximate selection with relative accuracy λ>0 asks for any element whose true rank differs from r by at most An. Our main results are: (1) For all t ≥(log log n ) 4, approximate selection problems of size n can be solved in O(t) time with optimal speedup with relative accuracy \(2^{{{ - t} \mathord{\left/{\vphantom {{ - t} {\left( {\log \log n} \right)}}} \right. \kern-\nulldelimiterspace} {\left( {\log \log n} \right)}}^4 }\); no deterministic PRAM algorithm for approximate selection with a running time below Ο (log n /log log n ) was previously known. (2) Exact selection problems of size n can be solved in O (log n /log log n ) time with O(n log log n /log n ) processors. This running time is the best possible (using only a polynomial number of processors), and the number of processors is optimal for the given running time (optimal speedup); the best previous algorithm achieves optimal speedup with a running time of O (log n log * n /log log n ).

Authors

• Shiva Chaudhuri
• Torben Hagerup
• Rajeev Raman

Keywords

No keywords are indexed for this paper.