Approximating Nash Social Welfare by Matching and Local Search

Jugal Garg, Edin Husić, Wenzheng Li +2

For any $\epsilon >0$, we give a simple, deterministic $(4+\epsilon )$-approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. We also co…