Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps
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.
Authors
- Ruilong Zhang (ORCID: https://orcid.org/0000-0002-4859-2661)
- Xiaohui Bei (ORCID: https://orcid.org/0000-0002-0870-5019)
- Shi Li (ORCID: https://orcid.org/0000-0002-7540-6852)
- Yang Hu (ORCID: https://orcid.org/0009-0004-3632-4506)
- Yuda Feng
Institutions
- City University of Hong Kong (HK)
- Nanyang Technological University (SG)
- City College of Dongguan University of Technology (CN)
- Nanjing University (CN)
- Tsinghua University (CN)
Publication Details
- Published
- 2026-06-09
- DOI
- https://doi.org/10.1145/3798129.3800909
- Primary Topic
- Risk and Portfolio Optimization
- Type
- article
- Field-Weighted Citation Impact
- 0.00