@online{Akrami2106.14816,
TITLE = {Nash Social Welfare for 2-value Instances},
AUTHOR = {Akrami, Hannaneh and Ray Chaudhury, Bhaskar and Mehlhorn, Kurt and Shahkarami, Golnoosh and Vermande, Quentin},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2106.14816},
EPRINT = {2106.14816},
EPRINTTYPE = {arXiv},
YEAR = {2021},
ABSTRACT = {We study the problem of allocating a set of indivisible goods among agents<br>with 2-value additive valuations. Our goal is to find an allocation with<br>maximum Nash social welfare, i.e., the geometric mean of the valuations of the<br>agents. We give a polynomial-time algorithm to find a Nash social welfare<br>maximizing allocation when the valuation functions are integrally 2-valued,<br>i.e., each agent has a value either $1$ or $p$ for each good, for some positive<br>integer $p$. We then extend our algorithm to find a better approximation factor<br>for general 2-value instances.<br>},
}