Shi Li

activity

20102023

most citedA Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2

32 citations · 98 across the 32 of their papers we have counts for

collaborators

Showing 2014Show all

3 papers · 1 filter

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

On $(1, ε)$ -Restricted Assignment Makespan Minimization

Deeparnab Chakrabarty, Sanjeev Khanna, Shi Li

Makespan minimization on unrelated machines is a classic problem in approximation algorithms. No polynomial time $(2 - δ)$ -approximation algorithm is known for the problem for consta…

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…

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

On (1,ε)-Restricted Assignment Makespan Minimization

On Uniform Capacitated k-Median Beyond the Natural LP Relaxation

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

On $(1, ε)$ -Restricted Assignment Makespan Minimization

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