Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps
Abstract
We study the problem of allocating items to agents with submodular valuations with the goal of maximizing the weighted Nash social welfare (NSW). The best-known results for unweighted and weighted objectives are the (4+є) approximation given by Garg, Husic, Li, Végh, and Vondrák [STOC 2023] and the (233+є) approximation given by Feng, Hu, Li, and Zhang [STOC 2025], respectively.
Fields of Study & Subjects
Risk and Portfolio Optimization
Stochastic processes and financial applications
Probability and Risk Models
Publication details
- Pages
- 2052–2063
- Publication date
- 9 June 2026
- Language
- EN