MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Kaligosi, Kanela
Mehlhorn, Kurt
Munro, J. Ian
Sanders, Peter		dblp
dblp
dblp
dblp
Not MPG Author(s):
Munro, J. Ian
Sanders, Peter
Editor(s):
Caires, Luis
Italiano, Giuseppe F.
Monteiro, Luís
Palamidessi, Catuscia
Yung, Moti		dblp
dblp
dblp
dblp
dblp
BibTeX cite key*:
mehlhorn05o
Title, Booktitle
Title*:
Towards Optimal Multiple Selection
Mehlhorn_a_2005_o.pdf (188.53 KB)
Booktitle*:
Automata, languages and programming : 32nd International Colloquim, ICALP 2005
Event, URLs
Conference URL::
Downloading URL:
http://www.springerlink.com/content/1j18jlpctfe3dmqv/fulltext.pdf
http://dx.doi.org/10.1007/11523468_9
Event Address*:
Lisbon, Portugal
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
11 July 2005
Event End Date:
15 July 2005
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
3580
Number:
Month:
Pages:
103-114
Year*:
2005
VG Wort Pages:
ISBN/ISSN:
3-540-27580-0
Sequence Number:
DOI:
10.1007/11523468_9
Note, Abstract, ©
(LaTeX) Abstract:
The multiple selection problem asks for the elements of rank r1, r2, ..., rk from a linearly ordered set of n elements. Let B denote the information theoretic lower bound on the number of element comparisons needed for multiple selection. We first show that a variant of multiple quickselect — a well known, simple, and practical generalization of quicksort — solves this problem with expected comparisons. We then develop a deterministic divide-and-conquer algorithm that solves the problem in time and element comparisons.
HyperLinks / References / URLs:
http://www.springerlink.com/content/1j18jlpctfe3dmqv/?p=646827d6f77f47fc85d7197c467864ef&pi=82
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{mehlhorn05o,
AUTHOR = {Kaligosi, Kanela and Mehlhorn, Kurt and Munro, J. Ian and Sanders, Peter},
 EDITOR = {Caires, Luis and Italiano, Giuseppe F. and Monteiro, Lu{\'i}s and Palamidessi, Catuscia and Yung, Moti},
 TITLE = {Towards Optimal Multiple Selection},
 BOOKTITLE = {Automata, languages and programming : 32nd International Colloquim, ICALP 2005},
 PUBLISHER = {Springer},
 YEAR = {2005},
 VOLUME = {3580},
 PAGES = {103--114},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Lisbon, Portugal},
 ISBN = {3-540-27580-0},
 DOI = {10.1007/11523468_9},
}

Entry last modified by Anja Becker, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Christine Kiesel		Created
08/07/2006 06:20:43 AM
Revisions
14.
13.
12.
11.
10.		Editor(s)
Anja Becker
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
05.02.2008 15:53:47
04.10.2006 08:39:51
29.09.2006 09:23:52
14.09.2006 13:32:50
14.09.2006 13:26:17