Tales of Huffman
<|reference_start|>Tales of Huffman: We study the new problem of Huffman-like codes subject to individual restrictions on the code-word lengths of a subset of the source words. These are prefix codes with minimal expected code-word length for a random source where additionally the code-word lengths of a subset of the source words is prescribed, possibly differently for every such source word. Based on a structural analysis of properties of optimal solutions, we construct an efficient dynamic programming algorithm for this problem, and for an integer programming problem that may be of independent interest.<|reference_end|>
@article{vitanyi2006tales,
    title={Tales of Huffman},
    author={Paul M.B. Vitanyi (CWI and University of Amsterdam), Zvi Lotker (Ben
  Gurion University, Beer Sheva)},
    journal={arXiv preprint arXiv:cs/0612133},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0612133},
    primaryClass={cs.IT cs.CC math.IT}
}