EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Approximating Nash Social Welfare by Matching and Local Search

Jugal Garg, Edin Husić, Wenzheng Li, László Végh, Jan Vondrák

Journal of the ACM · 30.06.2026 · 73 (3) · 1-25

DOI: 10.1145/3807505 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 16.06.2026. Verfasst von Jugal Garg und 4 weiteren Autor:innen. Die Arbeit nennt 62 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NSF, European Research Council, SNSF.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

For any ɛ > 0, we give a simple, deterministic (4+ɛ)-approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. We also consider the asymmetric variant of the problem, where the objective is to maximize the weighted geometric mean of agents’ valuations, and give an e(ω + 2 + ɛ)-approximation if the ratio between the largest weight and the average weight is at most ω. We also show that the 1/2-EFX envy-freeness property can be attained simultaneously with a constant-factor approximation. More precisely, we can find an allocation in polynomial time that is both 1/2-EFX and an (8+ɛ)-approximation to the symmetric NSW problem under submodular valuations.

Förderung

  • NSF
  • European Research Council
  • SNSF

Zitieren

APA

Garg, J., Husić, E., Li, W., Végh, L., & Vondrák, J. (2026). Approximating Nash Social Welfare by Matching and Local Search. Journal of the ACM, 73(3), 1-25. https://doi.org/10.1145/3807505

Vancouver

Garg J, Husić E, Li W, Végh L, Vondrák J. Approximating Nash Social Welfare by Matching and Local Search. Journal of the ACM. 2026;73(3):1-25. doi:10.1145/3807505

BibTeX
@article{Garg2026,
  author = {Garg, Jugal and Husić, Edin and Li, Wenzheng and Végh, László and Vondrák, Jan},
  title = {Approximating Nash Social Welfare by Matching and Local Search},
  journal = {Journal of the ACM},
  year = {2026},
  volume = {73},
  number = {3},
  pages = {1--25},
  doi = {10.1145/3807505}
}
Kostenlos starten →