English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Approximate and exact deterministic parallel selection

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.

Item is

Files

show Files
hide Files
:
MPI-I-93-118.pdf (Any fulltext), 8MB
Name:
MPI-I-93-118.pdf
Description:
-
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Chaudhuri, Shiva1, Author           
Hagerup, Torben1, Author           
Raman, Rajeev1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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\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}})$.

Details

show
hide
Language(s): eng - English
 Dates: 1993
 Publication Status: Issued
 Pages: 10 p.
 Publishing info: Saarbrücken : Max-Planck-Institut für Informatik
 Table of Contents: -
 Rev. Type: -
 Identifiers: URI: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/93-118
Report Nr.: MPI-I-93-118
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Research Report / Max-Planck-Institut für Informatik
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -