@article{Akrami_Chaudhury_Hoefer_Mehlhorn_Schmalhofer_Shahkarami_Varricchio_Vermande_Wijland_2022, title={Maximizing Nash Social Welfare in 2-Value Instances}, volume={36}, url={https://ojs.aaai.org/index.php/AAAI/article/view/20402}, DOI={10.1609/aaai.v36i5.20402}, abstractNote={We consider the problem of maximizing the Nash social welfare when allocating a set G of indivisible goods to a set N of agents. We study instances, in which all agents have 2-value additive valuations: The value of every agent for every good is either p or q, where p and q are integers and p<q. In this work, we design an algorithm to compute an optimal allocation in polynomial time if p divides q, i.e., when p=1 and q is an integer after appropriate scaling. The problem is NP-hard whenever p and q are coprime and p>2. In terms of approximation, we present positive and negative results for general p and q. We show that our algorithm obtains an approximation ratio of at most 1.0345. Moreover, we prove that the problem is APX-hard, with a lower bound of 1.000015 achieved at p/q = 4/5.}, number={5}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Akrami, Hannaneh and Chaudhury, Bhaskar Ray and Hoefer, Martin and Mehlhorn, Kurt and Schmalhofer, Marco and Shahkarami, Golnoosh and Varricchio, Giovanna and Vermande, Quentin and Wijland, Ernest van}, year={2022}, month={Jun.}, pages={4760-4767} }