APX-hardness of maximizing Nash social welfare with indivisible items

作者：Lee Euiwoong^*

来源：Information Processing Letters, 2017, 122: 17-20.

DOI：10.1016/j.ipl.2017.01.012

• Approximation algorithms
• Nash social welfare
• Hardness of approximation
• APX-hardness

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.

• 出版日期2017-6