内容：

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.

人物介绍：

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.