32 citations · 98 across the 32 of their papers we have counts for
37 papers
Polylogarithmic Approximation for Robust s-t Path
Shi Li, Chenyang Xu, Ruilong Zhang
The paper revisits the robust - path problem, one of the most fundamental problems in robust optimization. In the problem, we are given a directed graph with vertices and…
Degrees and Network Design: New Problems and Approximations
Michael Dinitz, Guy Kortsarz, Shi Li
While much of network design focuses mostly on cost (number or weight of edges), node degrees have also played an important role. They have traditionally either appeared as an obje…
Online Food Delivery to Minimize Maximum Flow Time
Xiangyu Guo, Shi Li, Kelin Luo +1
We study a common delivery problem encountered in nowadays online food-ordering platforms: Customers order dishes online, and the restaurant delivers the food after receiving the o…
Polynomial Integrality Gap of Flow LP for Directed Steiner Tree
Shi Li, Bundit Laekhanukit
In the Directed Steiner Tree (DST) problem, we are given a directed graph on vertices with edge-costs , a root vertex , and a se…
Robust High Dimensional Expectation Maximization Algorithm via Trimmed Hard Thresholding
Di Wang, Xiangyu Guo, Shi Li +1
In this paper, we study the problem of estimating latent variable models with arbitrarily corrupted samples in high dimensional space ({\em i.e.,} ) where the underlying pa…
Estimating Stochastic Linear Combination of Non-linear Regressions Efficiently and Scalably
Di Wang, Xiangyu Guo, Chaowen Guan +2
Recently, many machine learning and statistical models such as non-linear regressions, the Single Index, Multi-index, Varying Coefficient Index Models and Two-layer Neural Networks…
Consistent -Median: Simpler, Better and Robust
Xiangyu Guo, Janardhan Kulkarni, Shi Li +1
In this paper we introduce and study the online consistent -clustering with outliers problem, generalizing the non-outlier version of the problem studied in [Lattanzi-Vassilvits…
Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints
Janardhan Kulkarni, Shi Li, Jakub Tarnawski +1
We consider the classic problem of scheduling jobs with precedence constraints on a set of identical machines to minimize the makespan objective function. Understanding the exact a…
Towards PTAS for Precedence Constrained Scheduling via Combinatorial Algorithms
Shi Li
We study the classic problem of scheduling precedence constrained unit-size jobs on machines so as to minimize the makespan. In a recent breakthrough, Levey and Roth…
Covering the Relational Join
Shi Li, Sai Vikneshwar Mani Jayaraman, Atri Rudra
In this paper, we initiate a theoretical study of what we call the join covering problem. We are given a natural join query instance on attributes and relations $(R_i)_…
Topology Dependent Bounds For FAQs
Michael Langberg, Shi Li, Sai Vikneshwar Mani Jayaraman +1
In this paper, we prove topology dependent bounds on the number of rounds needed to compute Functional Aggregate Queries (FAQs) studied by Abo Khamis et al. [PODS 2016] in a synchr…
The Power of Recourse: Better Algorithms for Facility Location in Online and Dynamic Models
Xiangyu Guo, Janardhan Kulkarni, Shi Li +1
In this paper we study the facility location problem in the online with recourse and dynamic algorithm models. In the online with recourse model, clients arrive one by one and our…
Facility Location Problem in Differential Privacy Model Revisited
Yunus Esencayi, Marco Gaboardi, Shi Li +1
In this paper we study the uncapacitated facility location problem in the model of differential privacy (DP) with uniform facility cost. Specifically, we first show that, under the…
On Approximating Degree-Bounded Network Design Problems
Xiangyu Guo, Guy Kortsarz, Bundit Laekhanukit +3
Directed Steiner Tree (DST) is a central problem in combinatorial optimization and theoretical computer science: Given a directed graph with edge costs $c \in \mathbb{R}…
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…
Constant Approximation for -Median and -Means with Outliers via Iterative Rounding
Ravishankar Krishnaswamy, Shi Li, Sai Sandeep
In this paper, we present a new iterative rounding framework for many clustering problems. Using this, we obtain an -approximation algorithm for -median…
Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations
Shi Li
We study approximation algorithms for scheduling problems with the objective of minimizing total weighted completion time, under identical and related machine models with job prece…
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 time periods and all dema…
Tight Network Topology Dependent Bounds on Rounds of Communication
Arkadev Chattopadhyay, Michael Langberg, Shi Li +1
We prove tight network topology dependent bounds on the round complexity of computing well studied -party functions such as set disjointness and element distinctness. Unlike the…