Name
Abstract | ||
|---|---|---|
We study the problem of allocating m items to n agents subject to maximizing the Nash social welfare (NSW) objective. We write a novel convex programming relaxation for this problem, and we show that a simple randomized rounding algorithm gives a 1/e approximation factor of the objective, breaking the 1/2e^(1/e) approximation factor of Cole and Gkatzelis.Our main technical contribution is an extension of Gurvitsu0027s lower bound on the coefficient of the square-free monomial of a degree m-homogeneous stable polynomial on m variables to all homogeneous polynomials. We use this extension to analyze the expected welfare of the allocation returned by our randomized rounding algorithm. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.4230/LIPIcs.ITCS.2017.36 | conference on innovations in theoretical computer science |
DocType | Volume | Citations |
Conference | abs/1609.07056 | 2 |
PageRank | References | Authors |
0.40 | 5 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nima Anari | 1 | 79 | 14.83 |
| Shayan Oveis Gharan | 2 | 323 | 26.63 |
| Amin Saberi | 3 | 2824 | 224.27 |
| mohit singh | 4 | 515 | 38.42 |