论文标题
贪婪的最小熵耦合的更严格的近似保证
A Tighter Approximation Guarantee for Greedy Minimum Entropy Coupling
论文作者
论文摘要
我们检查了最小熵耦合问题，其中必须找到具有给定分布组的最小熵变量$ s = \ {p_1，\ dots，p_m \} $作为其边缘。尽管此问题是NP硬化，但以前的工作提出了具有不同近似保证的算法。在本文中，我们表明[Kocaoglu等人，AAAI'17]的贪婪耦合算法始终在$ \ log_2（e）$（$ \ of 1.44 $）位置，最小熵耦合。在此过程中，我们表明贪婪耦合的熵由$ h \ left（\ bigwedge s \ right） + \ log_2（e）$限制。这改善了以前最著名的近似保证，$ 2 $位的位置[li，ieee trans。 inf。理论'21]。此外，我们通过证明没有任何常数$ c <\ log_2（e）$的算法在$ h \ left（\ bigwedge s \ right） + c $上所限制的算法来表明我们的分析很紧张。此外，我们研究了贪婪耦合算法的特殊实例，这是最佳的。
We examine the minimum entropy coupling problem, where one must find the minimum entropy variable that has a given set of distributions $S = \{p_1, \dots, p_m \}$ 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 $\log_2(e)$ ($\approx 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\left(\bigwedge S \right) + \log_2(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 $H\left(\bigwedge S \right) + c$ for any constant $c<\log_2(e)$. Additionally, we examine a special class of instances where the greedy coupling algorithm is exactly optimal.
