|
Computer Science 2015
APX-Hardness of Maximizing Nash Social Welfare with Indivisible ItemsAbstract: 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.
|