32 citations · 98 across the 32 of their papers we have counts for
31 papers · 1 filter
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…
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…
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}…
-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…
Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-Uniform Distributions
Sungjin Im, Shi Li
In this paper we consider the classic scheduling problem of minimizing total weighted completion time on unrelated machines when jobs have release times, i.e, $R | r_{ij} | \sum_j…
Improved Approximation for Node-Disjoint Paths in Planar Graphs
Julia Chuzhoy, David H. K. Kim, Shi Li
We study the classical Node-Disjoint Paths (NDP) problem: given an -vertex graph and a collection of pairs of vertices of called deman…
Constant Approximation for Capacitated -Median with -Capacity Violation
Gökalp Demirci, Shi Li
We study the Capacitated k-Median problem for which existing constant-factor approximation algorithms are all pseudo-approximations that violate either the capacities or the upper…
On the computational complexity of minimum-concave-cost flow in a two-dimensional grid
Shabbir Ahmed, Qie He, Shi Li +1
We study the minimum-concave-cost flow problem on a two-dimensional grid. We characterize the computational complexity of this problem based on the number of rows and columns of th…
Approximating capacitated -median with open facilities
Shi Li
In the capacitated -median (\CKM) problem, we are given a set of facilities, each facility with a capacity , a set of clients, a metric over $F \cup C…
On -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 -approximation algorithm is known for the problem for consta…