文章基本信息

标题：Nash Social Welfare, Matrix Permanent, and Stable Polynomials
本地全文：下载
作者：Nima Anari ; Shayan Oveis Gharan ; Amin Saberi 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：67
页码：36:1-36:12
DOI：10.4230/LIPIcs.ITCS.2017.36
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 Gurvits's 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.
关键词：Nash Welfare; Permanent; Matching; Stable Polynomial; Randomized Algorithm; Saddle Point