Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

Maximizing Nash Social Welfare in 2-Value Instances

MPG-Autoren
/persons/resource/persons263365

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

/persons/resource/persons225687

Ray Chaudhury,  Bhaskar
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;

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)

arXiv:2107.08965.pdf
(Preprint), 330KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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


Zitierlink: https://hdl.handle.net/21.11116/0000-000C-2000-F
Zusammenfassung
We consider the problem of maximizing the Nash social welfare when allocating
a set $\mathcal{G}$ of indivisible goods to a set $\mathcal{N}$ of agents. We
study instances, in which all agents have 2-value additive valuations: The
value of every agent $i \in \mathcal{N}$ for every good $j \in \mathcal{G}$ is
$v_{ij} \in \{p,q\}$, for $p,q \in \mathbb{N}$, $p \le q$. Maybe surprisingly,
we design an algorithm to compute an optimal allocation in polynomial time if
$p$ divides $q$, i.e., when $p=1$ and $q \in \mathbb{N}$ 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$.