Heuristics for optimum binary search trees and minimum weight triangulation problems (Q1263993)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Heuristics for optimum binary search trees and minimum weight triangulation problems |
scientific article |
Statements
Heuristics for optimum binary search trees and minimum weight triangulation problems (English)
0 references
1989
0 references
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.
0 references
optimum binary search trees
0 references
minimum length
0 references
partition of polygons
0 references
heuristics for triangulation of polygons
0 references