neal young / Golin12Huffman

SIAM Journal on Computing 41(3):684713(2012); STOC'02We study the generalization of Huffman Coding in which codeword letters have nonuniform costs (as in Morse code, where the dash is twice as long as the dot). Despite previous work by many authors including Richard Karp [1961] and Kurt Mehlhorn [1980], the problem is not known to be NPhard, nor was it previously known to have a constantfactor approximation algorithm. The paper describes a polynomialtime approximation scheme (PTAS) for the problem. The algorithm computes a $(1+\epsilon)$approximate solution in time $O(n + f(\epsilon) \log^3 n)$, where $n$ is the input size.Journal version of [2002].
© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.