arXiv Open Access 2021

A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations

Wenzheng Li Jan Vondrák

Lihat Sumber

Abstrak

We present a $380$-approximation algorithm for the Nash Social Welfare problem with submodular valuations. Our algorithm builds on and extends a recent constant-factor approximation for Rado valuations.

Topik & Kata Kunci

cs.GT cs.DS

Penulis (2)

Wenzheng Li

Jan Vondrák

Format Sitasi

APA MLA BibTeX

Li, W., Vondrák, J. (2021). A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations. https://arxiv.org/abs/2103.10536

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2021
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓