A Tighter Approximation Guarantee for Greedy Minimum Entropy Coupling

Abstract

We examine the minimum entropy coupling problem, where one must find the minimum entropy variable that has a given set of distributions S = {p1,...,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 H(⋀S) + 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 constructing sets of distributions where the entropy of the minimum entropy coupling can be arbitrarily close to H(⋀S) + log2(e). Additionally, we examine a special class of instances where the greedy coupling algorithm is exactly optimal.