Trees with Minimum Weighted Path Length:Optimal Lopsided Trees

Optimal Lopsided Trees

The problem of finding optimal prefix-free codes for unequal letter costs consists of finding a minimal cost prefix-free code in which the encoding alphabet consists of unequal cost (length) letters, of lengths α and β, α β. We restrict ourselves here only to binary trees.

The code is represented by a lopsided tree, in the same way as a Huffman tree represents the solution of the Huffman coding problem. Despite the similarity, the case of unequal letter costs is much harder then the classical Huffman problem; no polynomial time algorithm is known for general letter costs, despite a rich literature on the problem, e.g., [4, 15]. However there are known polynomial time algorithms when α and β are integer constants [15].

The problem of finding the minimum cost tree in this case was first studied by Karp [27] in 1961 who solved the problem by reduction to integer linear programming, yielding an algorithm exponential in both n and β. Since that time there has been much work on various aspects of the problem such as; bounding the cost of the optimal tree, Altenkamp and Mehlhorn [2], Kapoor and Reingold [26] and Savari [8]; the restriction to the special case when all of the weights are equal, Cot [10], Perl Gary and Even [45], and Choi and Golin [9]; and approximating the optimal solution, Gilbert [13]. Despite all of these efforts it is still, surprisingly, not even known whether the basic problem is polynomial-time solvable or in NP -complete.

Golin and Rote [15] describe an O(nβ+2)-time dynamic programming algorithm that constructs the tree in a top-down fashion.

This has been improved using a different approach (monotone-matrix concepts, e.g., the Monge property and the SMAWK algorithm [7].

THEOREM 14.10 [6] Optimal lopsided trees can be constructed in O(nβ ) time.

This is the the most efficient known algorithm for the case of small β; in practice the letter costs are typically small (e.g., Morse codes).

Recently a scheme of an efficient approximating algorithm has been given.

THEOREM 14.11 [24]

There is a polynomial time approximation scheme for optimal lopsided trees.

Comments

Popular posts from this blog

Data Structure Visualization:Introduction and Value of Data Structure Rendering

Binary Space Partitioning Trees:BSP Tree as a Hierarchy of Regions.

Drawing Trees:HV-Layout