mlsanityData to 14 Oct 2026

APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items

arXiv 1507.01159 ↗First posted 5 Jul 2015cs.CC cs.DS cs.GTcited by 3

Not on the map. Why?

Abstract (arXiv)

We study the problem of allocating a set of indivisible items to agents with additive utilities to maximize the Nash social welfare. Cole and Gkatzelis recently proved that this problem admits a constant factor approximation. We complement their result by showing that this problem is APX-hard.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). First posted on arXiv 5 Jul 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 1; 2023: 0; 2024: 0; 2025: 0; 2026: 1.

3 papers.

  1. 2022Welfare and Fairness in Multi-objective Reinforcement Learningcited by 20
  2. 2021PROPm Allocations of Indivisible Goods to Multiple Agentscited by 1
  3. 2026EF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, and Experimentscited by 0