Ugo Vaccaro, University of Salerno, Italy

Minimum Entropy Joint Distributions with Fixed Marginals: Algorithms and Applications

Given two arbitrarily distributed random variables X and Y, we study the problem of finding a minimum entropy joint distribution of X and Y , having the prescribed marginals. This problem is NP- hard, in general. We give an efficient algorithm to find a joint probability distribution of X and Y, with the given marginals, whose entropy exceeds the minimum possible by at most of one bit. We also discuss a few scenarios where this kind of optimization naturally arises. (This is joint work with F. Cicalese and L. Gargano).