内容简介：Historically, constructing optimal (minimum average search time) binary search trees (BSTs) is one of the canonical examples of dynamic programming. In 1971, Knuth described how to solve this problem in O(n^2) time, with input specifying the probability of the different successful and unsuccessful searches. While the trees constructed were binary, the comparisons used were ternary. Successful searches terminated at internal nodes and unsuccessful searches at leaves.
By contrast, in binary comparison trees (BCSTs), internal nodes perform binary comparisons; the search branches left or right depending upon the comparison outcome and all searches terminate at leaves. Polynomial algorithms exist for solving the optimal BCST problem restricted to successful searches. Hu and Tucker gave an O(n log n) algorithm when all comparisons are the inequality “<”; Anderson et. al. developed an O(n^4) algorithm when both “<” and “=” comparisons are allowed.
In this talk we present the first polynomial time algorithms for solving the optimal BCST problem when unsuccessful searches are included in the input and any set of comparisons are permitted. Our running times depend upon the comparisons allowed. If equality is not allowed, our algorithm runs in O(n log n) time; if equality is allowed, O(n^4). We also demonstrate O(n) time algorithms that yield almost optimal binary comparison trees, with tree cost within constant additive factor of optimal.
This is joint work with Marek Chrobak, Ian Munro and Neal Young.
个人简介：After receiving his doctorate from Princeton University in 1990, Dr Golin worked as a researcher in the Projet Algorithmes of the Institut National de Recherche en Informatique et en Automatique (INRIA) in Rocquencourt, France before arriving at HKUST in 1993. Since then, has also been a visiting researcher at the Max-Planck-Institut fur Informatik in Saarbrucken, Germany, INRIA-Sophia in France, AT&T Labs-Research, and DIMACS. In addition he served as the HKUST Associate Vice-President for Postgraduate Studies from 2011-2014.
More information please see:
https://www.cse.ust.hk/faculty/golin/
|
