Nie jesteś zalogowany |
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)
