English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We examine the minimum entropy coupling problem, where one must find theminimum entropy variable that has a given set of distributions $S = \{p_1,\dots, p_m \}$ as its marginals. Although this problem is NP-Hard, previousworks have proposed algorithms with varying approximation guarantees. In thispaper, 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 entropycoupling. In doing so, we show that the entropy of the greedy coupling isupper-bounded by $H\left(\bigwedge S \right) + \log_2(e)$. This improves thepreviously best known approximation guarantee of $2$ bits within the optimal[Li, IEEE Trans. Inf. Theory '21]. Moreover, we show our analysis is tight byproving 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 isexactly optimal.

A Tighter Approximation Guarantee for Greedy Minimum Entropy Coupling