A Better-than- Approximation Algorithm for Nash Social Welfare under Additive Valuations
arXiv:2607.13340
summary
The paper proposes an algorithm that achieves a (e^{1/e} − c) approximation, improving on the previous e^{1/e} bound, for maximizing Nash social welfare with additive valuations.
Abstract
We present an -approximation algorithm for maximizing Nash social welfare under additive valuations, for some constant . This result improves upon the previous best-known approximation factor of [Barman, Krishnamurthy and Vaish, EC 2018].
Topics & keywords
#nash social welfare#approximation algorithms#additive valuations#combinatorial optimization#theoretical computer sciencee^{1/e}approximation factoradditive valuationsNash social welfareconstant c