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). In particular, for selecting the k-th smallest item, or the set of~k smallest items, from a collection of m sorted lists we obtain a new optimal "output-sensitive" algorithm that performs only $O(m+\sum_{i=1}^m \log(k_i+1))$ comparisons, where k_i is the number of items of the i-th list that belong to the overall set of k smallest items.

Joint work with Haim Kaplan, L\'{a}szl\'{o} Kozma and Or Zamir.

Short Bio:

Uri Zwick is an Israeli computer scientist and mathematician known for his work on graph algorithms, in particular on distances in graphs and on the color-coding technique for subgraph isomorphism. With Howard Karloff, he is the namesake of the Karloff–Zwick algorithm for approximating the MAX-3SAT problem of Boolean satisfiability.He and his coauthors won the David P. Robbins Prize in 2011 for their work on the block-stacking problem.Zwick earned a bachelor's degree from the Technion – Israel Institute of Technology, and completed his doctorate at Tel Aviv University in 1989 under the supervision of Noga Alon. He is currently a professor of computer science at Tel Aviv University.