Campus Event Calendar
Event Entry
What and Who
Selection from heaps, row-sorted matrices and X + Y using soft heaps
Laszlo Kozma
TU Eindhoven
AG1 Mittagsseminar (own work)
AG 1, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 7 December 2017
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
We use soft heaps to obtain simpler optimal algorithms for selecting the k-th smallest item and the set of k smallest items, from a heap-ordered tree, from a collection of sorted lists, and from X + Y, where X and Y are two unsorted sets. Our results match, and in some ways extend and improve, classical results of Frederickson (1993) and Frederickson and Johnson (1982).
Joint work with Haim Kaplan, Or Zamir, and Uri Zwick.
Contact
Karl Bringmann
--email hidden
passcode not visible
logged in users only
Karl Bringmann, 11/27/2017 10:19
Karl Bringmann, 11/21/2017 12:24 -- Created document.
Karl Bringmann, 11/21/2017 12:24 -- Created document.