@inproceedings{299c2aed2c47439d89a355ad3dd56f33,
title = "Complexity and Approximation Schemes for Social Welfare Maximization in the High-Multiplicity Setting",
abstract = "We study the social welfare maximization problem in the high-multiplicity setting where agents and/or items are available in multiple types, provided that the numbers of types are small.We focus on the egalitarian and Nash social welfare maximization problems, and show that they are NP-hard even when the number of item types is a constant.Furthermore, we present two polynomial-time approximation schemes (PTAS), one for egalitarian social welfare with two item types, and one for Nash social welfare with any constant number of agent types.The first PTAS can be applied to the unrelated machine scheduling problem, thus partially solving an open question raised by Jansen and Maack in 2019.The second PTAS significantly improves upon the existing PTAS for identical agents.",
author = "Nguyen, \{Trung Thanh\} and Khaled Elbassioni and J{\"o}rg Rothe",
note = "Publisher Copyright: {\textcopyright} 2024 The Authors.; 27th European Conference on Artificial Intelligence, ECAI 2024 ; Conference date: 19-10-2024 Through 24-10-2024",
year = "2024",
month = oct,
day = "16",
doi = "10.3233/FAIA240881",
language = "British English",
series = "Frontiers in Artificial Intelligence and Applications",
publisher = "IOS Press BV",
pages = "3324--3331",
editor = "Ulle Endriss and Melo, \{Francisco S.\} and Kerstin Bach and Alberto Bugarin-Diz and Alonso-Moral, \{Jose M.\} and Senen Barro and Fredrik Heintz",
booktitle = "ECAI 2024 - 27th European Conference on Artificial Intelligence, Including 13th Conference on Prestigious Applications of Intelligent Systems, PAIS 2024, Proceedings",
address = "Netherlands",
}