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
Post a Comment