APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items
arXiv:1507.01159
Abstract
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.
6 pages