# MPI-I-93-118

## 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}})$.

Acknowledgement:** **

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.pdf | 8162 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: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1993-118

**BibTeX**
`@TECHREPORT{``ChaudhuriHagerupRaman93``,`

` 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},`

`}`