Greedy additive approximation algorithms for minimum-entropy coupling problem

Given two probability distributions p = (p_1 ,p_2 ,...,p_n ) and q = (q_1 ,q_2 ,...,q_m ) of two discrete random variables X and Y respectively, the minimum-entropy coupling problem is to find the minimum-entropy joint distribution among all possible joint distributions of X and Y having p and q as marginals. This problem is known to be NP-hard and recently have been proposed greedy algorithms that provide different guarantees, i.e. solutions that are local minimum [Kocaoglu et al. AAAI'17] and 1-bit approximation [Cicalese et al. ISIT'17]. In this paper, we show that the algorithm proposed by Kocaoglu et al. provides, in addition, a 1-bit approximation guarantee in the case of 2 variables. Then, we provide a general criteria for guaranteeing an additive approximation factor of 1 that might be of independent interest in other contexts where couplings are used.