Arrow Research search

Author name cluster

Rajeev Raman

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

16 papers
2 author rows

Possible papers

16

MFCS Conference 1993 Conference Paper

Approximate and Exact Deterministic Parallel Selection

  • Shiva Chaudhuri
  • Torben Hagerup
  • Rajeev Raman

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 ).

Details

FOCS Conference 1992 Conference Paper

Waste Makes Haste: Tight Bounds for Loose Parallel Sorting

  • Torben Hagerup
  • Rajeev Raman

Conventional parallel sorting requires the n input keys to be output in an array of size n, and is known to take Omega (log n/log log n) time using any polynomial number of processors. The lower bound does not apply to the more 'wasteful' convention of padded sorting, which requires the keys to be output in sorted order in an array of size (1+o(1))n. The authors give very fast randomised CRCW PRAM algorithms for several padded-sorting problems. Applying only pairwise comparisons to the input and using kn processors, where 2 >

Details