Nash Social Welfare and A Tale of Mathematical Programs
summary
Problem is NP-hard and APX-hard; presentation lays out concrete convex and nonconvex relaxations for Nash and weighted Nash social welfare, and ties them to determinant-maximization and matroid intersection. Key claims: a polynomial/stable-polynomial relaxation yields the known constant approximations for unweighted cases and a constant-factor (≈2) bound from a spending-restricted (Eisenberg–Gale/Shmyrev) view; the weighted case becomes nonconvex but a convex proxy adds KL-divergence dependence and currently gives only bounds exponential in that KL. Tools: convex programming, stability of polynomials, rounding via sparse forest supports, and questions about KKT/CLS hardness.
AI-written summary · about