# A Tighter Approximation Guarantee for Greedy Minimum Entropy Coupling

arXiv: https://arxiv.org/abs/2203.05108 · HTML: https://mlsanity.com/paper/2203.05108/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2022.

## Built on by (most cited first, 4 of 4)

- [Multimodal Learning Without Labeled Multimodal Data: Guarantees and Applications](https://mlsanity.com/paper/2306.04539/) (2023)
- [Minimum Entropy Coupling with Bottleneck](https://mlsanity.com/paper/2410.21666/) (2024)
- [Learning to Match Unpaired Data with Minimum Entropy Coupling](https://mlsanity.com/paper/2503.08501/) (2025)
- [Learning from Totally Unpaired Data via Minimum Conditional Entropy Coupling](https://mlsanity.com/paper/2605.16229/) (2026)

## Abstract (arXiv)

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.