de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Impressum Kontakt Einloggen

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

#### Approximate and exact deterministic parallel selection

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44233

Chaudhuri,  Shiva
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44564

Hagerup,  Torben
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45250

Raman,  Rajeev
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)

MPI-I-93-118.pdf
(beliebiger Volltext), 8MB

##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

Chaudhuri, S., Hagerup, T., & Raman, R.(1993). Approximate and exact deterministic parallel selection (MPI-I-93-118). Saarbrücken: Max-Planck-Institut für Informatik.

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