Heuristics for optimum binary search trees and minimum weight triangulation problems (Q1263993)

The article addresses the following problem: Construct optimum binary search trees, given a set of keys \(K_ 1<K_ 2<...<K_ n\) and the access probabilities, namely the special case with zero-key access probabilities (it means zero probability \(K_ i\) is the search argument and non zero probability the search argument lies in the interval \((K_ i,K_{i+1})).\) First, the authors proved one-to-one correspondence between zero-key access probability optimum binary search trees and the minimum weight triangulation of a special type of polygon (in fact they prove more general result concerning correspondence between (m-1)-way search trees and partition of certain type of polygons into m-gons). Then they show heuristics for triangulation of polygons of this type and translate them into corresponding ones for optimum binary search trees. Going other way, a lower bound on the approximation factor of the greedy heuristic for binary search trees also proved in the paper can be translated into a corresponding lower bound on the approximation factor of the greedy triangulation for corresponding polygons.