在这篇文章中，我们探讨了给定 $m \geq 2$ 个离散概率分布的情况下，如何有效计算最小熵耦合。最小熵耦合是指其边际分布与输入分布相同的最低熵联合分布。虽然计算最小熵耦合是 NP-hard 的问题，但近年来在设计近似算法方面取得了显著进展。之前的研究中，已知的最佳多项式时间算法的保证形式为：$H(\text{ALG}) \leq H(\text{OPT}) + c$，其中对于 $m=2$ 时，$c \approx 0.53$，而对于一般的 $m$，$c \approx 1.22$ [CKQGK '23]。一个主要的未解决问题是该任务是否是 APX-hard，或者是否存在多项式时间近似方案 (PTAS)。在本研究中，我们设计了一种算法，能够在运行时间为 $n^{O(\text{poly}(1/\varepsilon) \cdot \exp(m))}$ 的情况下生成熵满足 $H(\text{ALG}) \leq H(\text{OPT}) + \varepsilon$ 的耦合，证明了对于常数 $m$ 存在 PTAS。
博主点评： 本文在最小熵耦合的近似算法设计上取得了重要进展，展示了在复杂度理论中的新可能性。对于实际应用而言，能在合理时间内获得可接受的近似解，无疑将推动相关领域的发展。尤其是在处理多分布问题时，该算法的适用性值得关注。