research
∙
09/09/2023
A constant factor approximation for Nash social welfare with subadditive valuations
We present a constant-factor approximation algorithm for the Nash social...
share
research
∙
11/07/2022
Approximating Nash Social Welfare by Matching and Local Search
For any ε>0, we give a simple, deterministic (6+ε)-approximation algorit...
research
∙
03/18/2021
A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations
We present a 380-approximation algorithm for the Nash Social Welfare pro...
research
∙
01/06/2021
Estimating the Nash Social Welfare for coverage and other submodular valuations
We study the Nash Social Welfare problem: Given n agents with valuation ...
research
∙
02/21/2020
A polynomial lower bound on adaptive complexity of submodular maximization
In large-data applications, it is desirable to design algorithms with a ...
research
∙
11/03/2017
An Optimal Distributed (Δ+1)-Coloring Algorithm?
Vertex coloring is one of the classic symmetry breaking problems studied...
research
∙
10/28/2017