Abstract: We consider the problem of maximizing the Nash social welfare when allocating a set $\calG$ of indivisible goods to a set $\calN$ of agents. We study instances, in which all agents have 2-value additive valuations: The value of every agent $i \in \calN$ for every good $j \in \calG$ is $v_{ij} \in \{p,q\}$, for $p,q \in \NN$, $p \le 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 \in \NN$ after appropriate scaling. The problem is \classNP-hard whenever $p$ and $q$ are coprime and $p \ge 3$.



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 \classAPX-hard, with a lower bound of $1.000015$ achieved at $p/q = 4/5$.