A Tighter Approximation Guarantee for Greedy Minimum Entropy Coupling

We examine the minimum entropy coupling problem, where one must find the minimum entropy variable that has a given set of distributions S = p1, dots, pm as its marginals. Although this problem is NP-Hard, previous works have proposed algorithms with varying approximation guarantees. In this paper, we show that the greedy coupling algorithm of [Kocaoglu et al., AAAI'17] is always within log2(e) (≈ 1.44) bits of the minimum entropy coupling. In doing so, we show that the entropy of the greedy coupling is upper-bounded by Hleft(bigwedge S right) + log2(e). This improves the previously best known approximation guarantee of 2 bits within the optimal [Li, IEEE Trans. Inf. Theory '21]. Moreover, we show our analysis is tight by proving there is no algorithm whose entropy is upper-bounded by Hleft(bigwedge S right) + c for any constant c<log2(e). Additionally, we examine a special class of instances where the greedy coupling algorithm is exactly optimal.