The Construction of Huffman Codes is a Submodular ("Convex") Optimization Problem Over a Lattice of Binary Trees

DOI10.1137/S0097539796311077zbMath0967.94005MaRDI QIDQ4268846

No author found.

Publication date: 28 October 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

entropydynamic programmingconvexitycombinatorial optimizationcombinatorial inequalitieslatticesmajorizationgreedy algorithmsprefix codesHuffman codingsubmodular functionsFortuin-Kasteleyn-Ginibre (FKG) inequalityenumeration of treesMonge matricesSchur convex functionsquadrangle inequalityadaptive codingMoebius inversiontree imbalance

Mathematics Subject Classification ID

Trees (05C05) Combinatorics of partially ordered sets (06A07) Information theory (general) (94A15) Prefix, length-variable, comma-free codes (94A45) Coding theorems (Shannon theory) (94A24) Source coding (94A29)

Related Items (12)

The pruning-grafting lattice of binary trees ⋮ A branch-price-and-cut algorithm for the minimum evolution problem ⋮ A tutorial on the balanced minimum evolution problem ⋮ An information theory perspective on the balanced minimum evolution problem ⋮ A massively parallel branch-\&-bound algorithm for the balanced minimum evolution problem ⋮ Optimal \((0, 1)\)-matrix completion with majorization ordered objectives ⋮ The balanced minimum evolution problem under uncertain data ⋮ Compact mixed integer linear programming models to the minimum weighted tree reconstruction problem ⋮ Enumerating vertices of the balanced minimum evolution polytope ⋮ The Balanced Minimum Evolution Problem ⋮ The \(S\)-digraph optimization problem and the greedy algorithm ⋮ On the balanced minimum evolution polytope

This page was built for publication: The Construction of Huffman Codes is a Submodular ("Convex") Optimization Problem Over a Lattice of Binary Trees