Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update
Options:








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

URL of the conference:


URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section
Mehlhorn_a_2005_o.pdf
View attachments here: