Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Approximate and exact deterministic parallel selection

Chaudhuri, Shiva and Hagerup, Torben and Raman, Rajeev

MPI-I-93-118. May 1993, 10 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
The selection problem of size $n$ is,
given a set of $n$ elements drawn from an ordered
universe and an integer $r$ with $1\le r\le 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 $\lambda>0$ asks for any element
whose true rank differs from $r$ by at most $\lambda n$.
Our main results are:
(1) For all $t\ge(\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/{(\log\log n)^4}}}$;
no deterministic PRAM algorithm for approximate
selection with a running time below
$\Theta({{\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}})$.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-93-118.pdfMPI-I-93-118.pdf8162 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Chaudhuri, Shiva and Hagerup, Torben and Raman, Rajeev},
  TITLE = {Approximate and exact deterministic parallel selection},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-93-118},
  MONTH = {May},
  YEAR = {1993},
  ISSN = {0946-011X},