  Given a set of discrete probability distributions, the minimum entropy
coupling is the minimum entropy joint distribution that has the input
distributions as its marginals. This has immediate relevance to tasks such as
entropic causal inference for causal graph discovery and bounding mutual
information between variables that we observe separately. Since finding the
minimum entropy coupling is NP-Hard, various works have studied approximation
algorithms. The work of [Compton, ISIT 2022] shows that the greedy coupling
algorithm of [Kocaoglu et al., AAAI 2017] is always within $log_2(e) \approx
1.44$ bits of the optimal coupling. Moreover, they show that it is impossible
to obtain a better approximation guarantee using the majorization lower-bound
that all prior works have used: thus establishing a majorization barrier. In
this work, we break the majorization barrier by designing a stronger
lower-bound that we call the profile method. Using this profile method, we are
able to show that the greedy algorithm is always within $log_2(e)/e \approx
0.53$ bits of optimal for coupling two distributions (previous best-known bound
is within 1 bit), and within $(1 + log_2(e))/2 \approx 1.22$ bits for coupling
any number of distributions (previous best-known bound is within 1.44 bits). We
also examine a generalization of the minimum entropy coupling problem: Concave
Minimum-Cost Couplings. We are able to obtain similar guarantees for this
generalization in terms of the concave cost function. Additionally, we make
progress on the open problem of [Kova\v{c}evi\'c et al., Inf. Comput. 2015]
regarding NP membership of the minimum entropy coupling problem by showing that
any hardness of minimum entropy coupling beyond NP comes from the difficulty of
computing arithmetic in the complexity class NP. Finally, we present
exponential-time algorithms for computing the exactly optimal solution.
