×

On the convex hull of Huffman trees. (English) Zbl 1274.90322

Haouari, M. (ed.) et al., ISCO 2010. International symposium on combinatorial optimization. Papers based on the presentations at the symposium, Hammamet, Tunesia, March 24–26, 2010. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 36, 1009-1016 (2010).
Summary: A well-known kind of binary tree in information theory is Huffman tree. Given any linear objective function \(f\), Huffman has given an algorithm allowing to find an optimal Huffman tree minimizing \(f\). In this paper, we associate to each Huffman point of \(n\) nodes, a point in \(\mathbb{Q}_n\) called Huffman point whose components are the length of the path from the root of the tree to each leaf. In this paper, we study the Huffmanhedron, \(\mathrm{PH}_n\), which is the convex hull of the Huffman points in \(\mathbb{Q}_n\). In particular, we present a family of facet-defining inequalities for \(\mathrm{PH}_n\) whose coefficients form a Fibonacci sequence. We describe several lifting and composition methods which allow to derive new facet-defining inequalities from existing ones. Finally, we show that these methods together with the Fibonacci family of facet-defining inequalities characterize all facets of non-negative coefficients for \(\mathrm{PH}_n\) containing a deepest Huffman point, i.e., a permutation of the Huffman point \((n-1,n-1,n-2,\ldots,3,2,1)\).
For the entire collection see [Zbl 1236.90011].

MSC:

90C27 Combinatorial optimization
05C05 Trees
94A15 Information theory (general)
PDFBibTeX XMLCite
Full Text: Link

References:

[1] Huffman, D. A.: A method for the construction of minimum-redundancy codes. Procedings of the I.R.E. 40, 1098-1101 (1951)
[2] P. H. Schoute. Analytic treatment of the polytopes regularly derived from the regular polytopes, Verhandelingen der Koninklijke Akademie van Wetenschappen te Amsterdam, Vol. 3: Deel 11, Amsterdam 1911
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.