32 citations · 98 across the 32 of their papers we have counts for
6 papers · 1 filter
Distributed -Clustering for Data with Heavy Noise
Xiangyu Guo, Shi Li
In this paper, we consider the -center/median/means clustering with outliers problems (or the -center/median/means problems) in the distributed setting. Most previous di…
-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm
Fabrizio Grandoni, Bundit Laekhanukit, Shi Li
In the Directed Steiner Tree (DST) problem we are given an -vertex directed edge-weighted graph, a root , and a collection of terminal nodes. Our goal is to find a minimu…
Approximation algorithms for stochastic clustering
David G. Harris, Shi Li, Thomas Pensyl +2
We consider stochastic settings for clustering, and develop provably-good approximation algorithms for a number of these notions. These algorithms yield better approximation ratios…
A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time
Uriel Feige, Janardhan Kulkarni, Shi Li
We consider the classic scheduling problem of minimizing the total weighted flow-time on a single machine (min-WPFT), when preemption is allowed. In this problem, we are given a se…
Flow-time Optimization For Concurrent Open-Shop and Precedence Constrained Scheduling Models
Janardhan Kulkarni, Shi Li
Scheduling a set of jobs over a collection of machines is a fundamental problem that needs to be solved millions of times a day in various computing platforms: in operating systems…
On Facility Location with General Lower Bounds
Shi Li
In this paper, we give the first constant approximation algorithm for the lower bounded facility location (LBFL) problem with general lower bounds. Prior to our work, such algorith…