###
On the Hardness of Finding Optimal Multiple Preset Dictionaries

We show that the following simple compression problem is NP-hard:
given a collection of documents, find the pair of Huffman
dictionaries that minimizes the total compressed size of the
collection, where the best dictionary from the pair is used
to compress each document. We also show the NP-hardness of finding
optimal multiple preset dictionaries for LZ'77-based compression
schemes. Our reductions make use of the catalog segmentation problem,
a natural partitioning problem. Our results justify heuristic attacks
used in practice.