Helsinki Algorithms Seminar: "Selection from heaps, row-sorted matrices and X + Y using soft heaps" Laszlo Kozma

Weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design

Laszlo Kozma

Selection from heaps, row-sorted matrices and X + Y using soft heaps

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

This is joint work with Haim Kaplan, Or Zamir, and Uri Zwick.

**

Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.

Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.

Welcome!