Speaker: Prof. Uri Zwick Tel Aviv University
Time: 2009-04-16 15:00-2009-04-16 16:00
Venue: FIT Building 4-603, Tsinghua University
Download: Click!

Abstract:

Chazelle (JACM 47(6), 2000) devised an approximate meldable priority queue data structure, called _Soft Heaps_, and used it to obtain the fastest known deterministic comparison-based algorithm for computing minimum spanning trees, as well as some new algorithms for selection and approximate sorting problems. If n elements are inserted into a collection of soft heaps, then up to \eps n of the elements still contained in these heaps, for a given _error parameter_ \eps, may be _corrupted_, i.e., have their keys artificially increased. In exchange for allowing these corruptions, each soft heap operation is performed in O(\log 1/\eps}) amortized time.

We present a simplified implementation and analysis of soft heaps.

Joint work with Haim Kaplan and Robert Tarjan.

Short Bio:

Uri Zwick received his B.Sc. degree in Computer Science from the Technion, Israel Institute of Technology, and his M.Sc. and Ph.D. degrees in Computer Science from Tel Aviv University. He is currently a Professor of Computer Science in Tel Aviv University. His main research interests are: algorithms and complexity, combinatorial optimization, mathematical games, and recreational mathematics.