English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Maximizing Nash Social Welfare in 2-Value Instances: The Half-Integer Case

MPS-Authors
/persons/resource/persons263365

Akrami,  Hannaneh
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45021

Mehlhorn,  Kurt       
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons251338

Shahkarami,  Golnoosh
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

arXiv:2207.10949.pdf
(Preprint), 306KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Akrami, H., Ray Chaudhury, B., Hoefer, M., Mehlhorn, K., Schmalhofer, M., Shahkarami, G., et al. (2022). Maximizing Nash Social Welfare in 2-Value Instances: The Half-Integer Case. Retrieved from https://arxiv.org/abs/2207.10949.


Cite as: https://hdl.handle.net/21.11116/0000-000C-1FD5-2
Abstract
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 a good $g \in
G$ for an agent $i \in N$ is either $1$ or $s$, where $s$ is an odd multiple of
$\frac{1}{2}$ larger than one. We show that the problem is solvable in
polynomial time. Akrami et at. showed that this problem is solvable in
polynomial time if $s$ is integral and is NP-hard whenever $s = \frac{p}{q}$,
$p \in \mathbb{N}$ and $q\in \mathbb{N}$ are co-prime and $p > q \ge 3$. For
the latter situation, an approximation algorithm was also given. It obtains an
approximation ratio of at most $1.0345$. Moreover, the problem is APX-hard,
with a lower bound of $1.000015$ achieved at $\frac{p}{q} = \frac{5}{4}$. The
case $q = 2$ and odd $p$ was left open.
In the case of integral $s$, the problem is separable in the sense that the
optimal allocation of the heavy goods (= value $s$ for some agent) is
independent of the number of light goods (= value $1$ for all agents). This
leads to an algorithm that first computes an optimal allocation of the heavy
goods and then adds the light goods greedily. This separation no longer holds
for $s = \frac{3}{2}$; a simple example is given in the introduction. Thus an
algorithm has to consider heavy and light goods together. This complicates
matters considerably. Our algorithm is based on a collection of improvement
rules that transfers any allocation into an optimal allocation and exploits a
connection to matchings with parity constraints.