This paper investigates how to efficiently compute minimum-entropy couplings given $m \ge 2$ discrete probability distributions. The minimum-entropy coupling refers to the lowest entropy joint distribution whose marginals match the input distributions. While calculating minimum-entropy couplings is NP-hard, significant progress has been made in designing approximation algorithms. Previously, the best-known polynomial-time algorithms guarantee a form of $H(\text{ALG}) \le H(\text{OPT}) + c$, where $c \approx 0.53$ for $m=2$ and $c \approx 1.22$ for general $m$ [CKQGK '23]. A key open question is whether this task is APX-hard or if there exists a polynomial-time approximation scheme (PTAS). In this work, we design an algorithm that produces a coupling with entropy satisfying $H(\text{ALG}) \le H(\text{OPT}) + \varepsilon$ in running time $n^{O(\text{poly}(1/\varepsilon) \cdot \text{exp}(m))}$, proving that a PTAS exists for constant $m$.
Blogger's Review: This paper makes significant strides in the design of approximation algorithms for minimum-entropy couplings, showcasing new possibilities in complexity theory. The ability to obtain acceptable approximate solutions in reasonable time will undoubtedly advance related fields, especially in handling multi-distribution problems, making the applicability of this algorithm noteworthy.