On the Optimality of Huffman Trees
C. Roger Glassey, Richard M. Karp · SIAM Journal on Applied Mathematics · 1976
Huffman’s well-known algorithm for the construction of optimal search trees is shown to have a more general optimality property than was previously known. A corollary of this general optimality property yields explicitly the optimal policy for the dynamic programming recurrence $F( n ) = f( n ) + \min _{1\leqq j\leqq n - 1} [ {F( j ) + F( {n - j} )} ]$, where f is concave nondecreasing. Several one-dimensional search problems are described which give rise to this recurrence.