Article ID Journal Published Year Pages File Type
4950891 Information Processing Letters 2017 4 Pages PDF
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 [5] recently proved that this problem admits a constant factor approximation. We complement their result by showing that this problem is APX-hard.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
APX-hardness of maximizing Nash social welfare with indivisible items
Authors
,