Speaker: Ian Munro
, University of Waterloo
Title: Optimal search trees with 2-way comparisons
In 1971, Knuth gave an O(n2)-time algorithm for the classic problem of finding an optimal binary search tree. Knuth’s algorithm works only for search trees based on 3-way comparisons, but most modern programming languages and computers support only 2-way comparisons (<, = and >). Until this paper, the problem of finding an optimal search tree using 2-way comparisons remained open — poly-time algorithms were known only for restricted variants. We solve the general case, giving
(i) an O(n4)-time algorithm and
(ii) an O(n log n)-time additive-3 approximation algorithm.
This is joint work with Marek Chrobak, Mordecai Golin, and Neal E. Young