Shi Li

activity

20242026

most citedConstant Approximation for Weighted Nash Social Welfare with Submodular Valuations

1 citations · 1 across the 5 of their papers we have counts for

collaborators

Showing 2026Show all

3 papers · 1 filter

cs.DS2026

Iterative Randomized Rounding for Better-Than-2 k-Median Approximation

Jarosław Byrka, Yuhao Guo, Yang Hu +5

We study the classic $k$ -median problem and refine the iterative rounding framework recently introduced by Byrka, Guo, Hu, Li, Wan, and Wang [FOCS'26], which yields a $(2+\varepsil…

cs.DS2026

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 $(e^{1/ e} \approx 1.445)$ -approximation via the rounding a…

cs.DS2026

$k$ -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 $k$ -clustering. As a starting point, we obtain an iterative round…

Iterative Randomized Rounding for Better-Than-2 k-Median Approximation

New Convex Programming Technique for Nash Social Welfare and Scheduling

k-Clustering via Iterative Randomized Rounding

$k$ -Clustering via Iterative Randomized Rounding