Shi Li

most citedOn Uniform Capacitated

k

-Median Beyond the Natural LP Relaxation

3 citations · 4 across the 3 of their papers we have counts for

collaborators

3 papers

cs.DS2016★ 1 cited

Constant Approximation Algorithm for Non-Uniform Capacitated Multi-Item Lot-Sizing via Strong Covering Inequalities

Shi Li

We study the non-uniform capacitated multi-item lot-sizing (\lotsizing) problem. In this problem, there is a set of demands over a planning horizon of $T$ time periods and all dema…

cs.DS2014

Approximating capacitated $k$ -median with $(1 + ε) k$ open facilities

Shi Li

In the capacitated $k$ -median (\CKM) problem, we are given a set $F$ of facilities, each facility $i \in F$ with a capacity $u_{i}$ , a set $C$ of clients, a metric $d$ over $F \cup C…

cs.DS2014★ 3 cited

On Uniform Capacitated $k$ -Median Beyond the Natural LP Relaxation

Shi Li

In this paper, we study the uniform capacitated $k$ -median problem. Obtaining a constant approximation algorithm for this problem is a notorious open problem; most previous works g…

Constant Approximation Algorithm for Non-Uniform Capacitated Multi-Item Lot-Sizing via Strong Covering Inequalities

Approximating capacitated k-median with (1+ε)k open facilities

On Uniform Capacitated k-Median Beyond the Natural LP Relaxation

Approximating capacitated $k$ -median with $(1 + ε) k$ open facilities

On Uniform Capacitated $k$ -Median Beyond the Natural LP Relaxation