In the standard Huffman coding problem, one is given a set of words and for each word a positive frequency. The goal is to encode each word w as a codeword c(w) over a given alphabet. The encoding must be prefix free (no codeword is a prefix of any other) and should minimize the weighted average codeword size . The problem has a well-known polynomial-time algorithm. 

This talk concerns the generalization in which the letters of the encoding alphabet may have non-uniform lengths. The goal is to minimize the weighted average codeword length. Despite previous work by many authors including Richard Karp [1961] and Kurt Mehlhorn [1980], the problem is not known to be NP-hard, nor was it previously known to have a polynomial-time approximation algorithm.  The talk will outline a polynomial-time approximation scheme (PTAS) for the problem from STOC 2002.