Minimum Delay Codes
Lawrence L. Larmore · SIAM Journal on Computing · 1989
Huffman’s algorithm finds a prefix-free binary code on a weighted alphabet which minimizes the expected length of the code string for a single symbol. A definition is given for the expected delay for a prefix-free binary code on a weighted alphabet: it is the expected time between a request to transmit the symbol and the completion of that transmission, assuming a channel with fixed capacity, where requests are queued. An $O(n^5 )$-time $O(n^3 )$-space convex hull algorithm is given that finds a code of minimal expected delay, where n is the size of the alphabet. It is conjectured that the algorithm has substantially lower time and space complexities in the worst case, and still lower in the average case. The heart of the proof of polynomial time complexity is the convex hull theorem, which states that under certain conditions a binary tree that minimizes one penalty measure can be changed to a binary tree that minimizes a second penalty measure in a carefully controlled sequence of changes called elementary shifts.