Name
Title | ||
|---|---|---|
Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities. |
Abstract | ||
|---|---|---|
Recently Cole and Gkatzelis [10] gave the first constant factor approximation algorithm for the problem of allocating indivisible items to agents, under additive valuations, so as to maximize the Nash social welfare (NSW). We give constant factor algorithms for a substantial generalization of their problem - to the case of separable, piecewise-linear concave utility functions. We give two such algorithms, the first using market equilibria and the second using the theory of real stable polynomials. Both approaches require new algorithmic ideas.
|
Year | DOI | Venue |
|---|---|---|
2018 | 10.5555/3174304.3175452 | SODA '18: Symposium on Discrete Algorithms
New Orleans
Louisiana
January, 2018 |
DocType | Volume | ISBN |
Conference | abs/1612.05191 | 978-1-61197-503-1 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nima Anari | 1 | 79 | 14.83 |
| Tung Mai | 2 | 16 | 1.80 |
| Shayan Oveis Gharan | 3 | 323 | 26.63 |
| Vijay V. Vazirani | 4 | 4942 | 702.02 |