Efficient $\epsilon$-approximate minimum-entropy couplings

Abstract

Given $m\ge 2$ discrete probability distributions over $n$ states each, the minimum-entropy coupling is the minimum-entropy joint distribution whose marginals are the same as the input distributions. Computing the minimum-entropy coupling is NP-hard, but there has been significant progress in designing approximation algorithms; prior to this work, the best known polynomial-time algorithms attain guarantees of the form $H(\mathrm{ALG})\le H(\mathrm{OPT})+c$, where $c\approx 0.53$ for $m=2$, and $c\approx 1.22$ for general $m$ [CKQGK '23]. A main open question is whether this task is APX-hard, or whether there exists a polynomial-time approximation scheme (PTAS). In this work, we design an algorithm that produces a coupling with entropy $H(\mathrm{ALG})\le H(\mathrm{OPT})+\epsilon$ in running time $n^{O(\mathrm{poly}(1/\epsilon )\cdot \exp (m))}$: showing a PTAS exists for constant $m$.