6 papers
New Convex Programming Technique for Nash Social Welfare and Scheduling
Yuda Feng, Weijiang Hu, Shi Li
We propose a new convex programming relaxation for the weighted Nash social welfare (NSW) problem that achieves a matching -approximation via the rounding a…
-Clustering via Iterative Randomized Rounding
JarosÅaw Byrka, Yuhao Guo, Yang Hu +3
In this work we propose a single rounding algorithm for the fractional solutions of the standard LP relaxation for -clustering. As a starting point, we obtain an iterative round…
Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps
Xiaohui Bei, Yuda Feng, Yang Hu +2
We study the problem of allocating items to agents with submodular valuations with the goal of maximizing the weighted Nash social welfare (NSW). The best-known results for unweigh…
Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations
Yuda Feng, Yang Hu, Shi Li +1
We study the problem of assigning items to agents so as to maximize the \emph{weighted} Nash Social Welfare (NSW) under submodular valuations. The best-known result for the problem…
A Note on Approximating Weighted Nash Social Welfare with Additive Valuations
Yuda Feng, Shi Li
We give the first -approximation for the weighted Nash Social Welfare problem with additive valuations. The approximation ratio we obtain is ,…
Logarithmic Approximations for Fair k-Set Selection
Shi Li, Chenyang Xu, Ruilong Zhang
We study the fair k-set selection problem where we aim to select sets from a given set system such that the (weighted) occurrence times that each element appears in these s…