Huffman Coding with Letter Costs: A Linear-Time Approximation Scheme
<|reference_start|>Huffman Coding with Letter Costs: A Linear-Time Approximation Scheme: We give a polynomial-time approximation scheme for the generalization of Huffman Coding in which codeword letters have non-uniform costs (as in Morse code, where the dash is twice as long as the dot). The algorithm computes a (1+epsilon)-approximate solution in time O(n + f(epsilon) log^3 n), where n is the input size.<|reference_end|>
@article{golin2002huffman,
    title={Huffman Coding with Letter Costs: A Linear-Time Approximation Scheme},
    author={Mordecai Golin, Claire Mathieu, Neal E. Young},
    journal={SIAM Journal on Computing 41(3):684-713(2012)},
    year={2002},
    doi={10.1137/100794092},
    archivePrefix={arXiv},
    eprint={cs/0205048},
    primaryClass={cs.DS}
}