A Better-than-$e^{1/e}$ Approximation Algorithm for Nash Social Welfare under Additive Valuations

Abstract

We present an $(e^{1/e}-c)$-approximation algorithm for maximizing Nash social welfare under additive valuations, for some constant $c>0$. This result improves upon the previous best-known approximation factor of $e^{1/e}$ [Barman, Krishnamurthy and Vaish, EC 2018].