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

Prelegent(ci)

Laszlo Kozma

Afiliacja

Freie Universität Berlin

Termin

21 lutego 2019 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

We use soft heaps to obtain simpler optimal algorithms for selecting the k-th smallest item from a heap-ordered tree, from a collection of sorted lists, and from X+Y. Our results match, and in some ways extend classical results of Frederickson (1993) and Frederickson and Johnson (1982).

Joint work with Haim Kaplan, Or Zamir, Uri Zwick. (SOSA 2019)

---