Research Interests
Broadly speaking, my research area is theoretical computer science. Specifically, I am interested in designing and analyzing approximation algorithms for NP-hard combinatorial problems. Main types of problems I worked on include facility location problems, network routing and design, scheduling, resource allocation problems, etc.
My research is supported by NSF grant CCF-1566356 and CCF-1717134.
Sample Papers
Here is the full list of my publications.
- O(log2k/loglog k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm (arxiv)[Abstract]
Bundit Laekhanukit, Fabrizio Grandoni and S. Li
Manuscript
In the Directed Steiner Tree (DST) problem we are given an n-vertex directed edge-weighted graph, a root r, and a collection of k terminal nodes. Our goal is to find a minimum-cost arborescence that contains a directed path from r to every terminal. We present an O(log2 k / log log k)-approximation algorithm for DST that runs in quasi-polynomial-time, i.e., in time npolylog k. With standard complexity assumptions, we show a matching lower bound of Ω(log2k / log log k) for the class of quasi-polynomial-time algorithms, meaning that our approximation ratio is asymptotically the best possible.
This is the first improvement on the DST problem since the classical quasi-polynomial-time O(log3 k) approximation algorithm by Charikar et al. [SODA'98 & J. Algorithms'99]. (The paper erroneously claims an O(log2k) approximation due to a mistake in prior work.)
Our approach is based on two main ingredients. First, we derive an approximation preserving reduction to the Label-Consistent Subtree (LCST) problem. The LCST instance has quasi-polynomial size and logarithmic height. We remark that, in contrast, Zelikovsky's heigh-reduction theorem [Algorithmica'97] used in all prior work on DST achieves a reduction to a tree instance of the related Group Steiner Tree (GST) problem of similar height, however losing a logarithmic factor in the approximation ratio.
Our second ingredient is an LP-rounding algorithm to approximately solve LCST instances, which is inspired by the framework developed by Rothvoss. We consider a Sherali-Adams lifting of a proper LP relaxation of LCST. Our rounding algorithm proceeds level by level from the root to the leaves, rounding and conditioning each time on a proper subset of label variables. The limited height of the tree and small number of labels on root-to-leaf paths guarantees that a small enough (namely, polylogarithmic) number of Sherali-Adams lifting levels is sufficient to condition up to the leaves.
- Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time
Shashwat Garg, Janardhan Kulkarni and S. Li
SODA 2019
- A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time (arxiv)[Abstract]
Uri Feige, Janardhan Kulkarni and S. Li
SODA 2019
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 set of n jobs, each job having a release time rj, a processing time pj, and a weight wj. The flow-time of a job is defined as the amount of time the job spends in the system before it completes; that is, Fj = Cj - rj, where Cj is the completion time of job. The objective is to minimize the total weighted flow-time of jobs.
This NP-hard problem has been studied quite extensively for decades. In a recent breakthrough, Batra, Garg, and Kumar presented a pseudo-polynomial time algorithm that has an O(1) approximation ratio. The design of a truly polynomial time algorithm, however, remained an open problem. In this paper, we show a transformation from pseudo-polynomial time algorithms to polynomial time algorithms in the context of min-WPFT. Our result combined with the result of Batra, Garg, and Kumar settles the long standing conjecture that there is a polynomial time algorithm with O(1)-approximation for min-WPFT.
- On Facility Location with General Lower Bounds (arxiv)[Abstract]
S. Li
SODA 2019
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 algorithms were only known for the special case where all facilities have the same lower bound: Svitkina [Svi10] gave a 448-approximation for the special case, and subsequently Ahmadian and Swamy [AS13] improved the approximation factor to 82.6.
As in [Svi10] and [AS13], our algorithm for LBFL with general lower bounds works by reducing the problem to the capacitated facility location (CFL) problem. To handle the challenges raised by the general lower bounds, it involves more reduction steps. One main complication is that after aggregating the clients and facilities at a few locations, each of these locations may contain many facilities with different opening costs and lower bounds. To address this issue, we introduce and reduce the LBFL problem to two intermediate problems called the LBFL with penalty (LBFL-P) and the transportation with configurable supplies and demands (TCSD) problems, which in turn can be reduced to the CFL problem.
- Distributed k-Clustering for Data with Heavy Noise [Abstract]
Xiangyu Guo and S. Li
NIPS 2018 (Spotlight)
In this paper, we consider the k-center/median/means clustering with outliers problems (or the (k, z)-center/median/means problems) in the distributed setting. Most previous distributed algorithms have their communication costs linearly depending on z, the number of outliers. Recently Guha et al. overcame this dependence issue by considering bi-criteria approximation algorithms that output solutions with 2z outliers. For the case where z is large, the extra z outliers discarded by the algorithms might be too large, considering that the data gathering process might be costly. In this paper, we improve the number of outliers to the best possible (1+ε)z, while maintaining the O(1)-approximation ratio and independence of communication cost on z. The problems we consider include the (k, z)-center problem, and (k, z)-median/means problems in Euclidean metrics. Implementation of the our algorithm for (k, z)-center shows that it outperforms many previous algorithms, both in terms of the communication cost and quality of the output solution.
- Constant Approximation for k-Median and k-Means with Outliers via Iterative Rounding (arxiv)[Abstract]
Ravishankar Krishnaswamy, S. Li and Sai Sandeep
STOC 2018
In this paper, we present a novel iterative rounding framework for many clustering problems. This leads to an (α1 + ε ≈ 7.08 + ε)-approximation algorithm for k-median with outliers, greatly improving upon the large implicit constant approximation ratio of Chen [Chen, SODA 08]. For k-means with outliers, we give an (α2 + ε ≈ 53 + ε)-approximation, which is the first O(1)-approximation for this problem. The iterative algorithm framework is very versatile; we show how it can be used to give α1- and (α1 + ε)-approximation algorithms for matroid median and knapsack median problems respectively, improving upon the previous best approximations ratios of 8 [Swamy, ACM Trans. Algorithms] and 17.46 [Byrka et al, ESA 2015].
The natural LP relaxation for the k-median/k-means with outliers problem has an unbounded integrality gap. In spite of this negative result, our iterative rounding framework shows that we can round an LP solution to an almost-integral solution of small cost, in which we have at most two fractionally open facilities. Thus, the LP integrality gap arises due to the gap between almost-integral and fully-integral solutions. Then, using a pre-processing procedure, we show how to convert an almost-integral solution to a fully-integral solution losing only a constant-factor in the approximation ratio. By further using a sparsification technique, the additive factor loss incurred by the conversion can be reduced to any ε > 0.
- Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations (arxiv)[Abstract]
S. Li
FOCS 2017
invited to a special issue of SICOMP
We study the approximation of scheduling problems with the objective of minimizing total weighted completion time, under many different machine models: identical machine model with job precedence constraints, with uniform and non-uniform job sizes, and related machine model with job precedence constraints. For these problems, we give approximation algorithms that improve upon the previous 15 to 20-year old state-of- art results. A major theme in these results is the use of time-indexed linear programming relaxations. These are natural LP relaxations for their respective problems, but are not studied explicitly in the literature.
We also consider the scheduling problem of minimizing total weighted completion time on unrelated machines. The recent breakthrough result of [Bansal-Srinivasan-Svensson, STOC 2016] gave a (1.5 - c)-approximation for the problem, based on some lift-and-project SDP relaxation. Our main result is that a (1.5 - c)-approximation can also be achieved using a natural and considerably simpler time-indexed LP relaxation for the problem. We hope the use of this time-indexed LP relaxation can provide new insights into this problem.
- On (1,ε)-Restricted Asgsignment Makespan Minimization (arxiv)[Abstract]
Deeparnab Chakrabarty, Sanjeev Khanna and S. Li
SODA 2015
Makespan minimization on unrelated machines is a classic problem in approximation algorithms. No polynomial time (2 - δ)-approximation algorithm is known for the problem for constant δ > 0. This is true even for certain special cases, most notably the restricted assignment problem where each job has the same load on any machine but can be assigned to one from a specified subset. Recently in a breakthrough result, Svensson [Sve11] proved that the integrality gap of a certain configuration LP relaxation is upper bounded by 1.95 for the restricted assignment problem; however, the rounding algorithm is not known to run in polynomial time.
In this paper we consider the (1,ε)-restricted assignment problem where each job is either heavy (pj = 1) or light (pj = ε), for some parameter ε > 0. Our main result is a (2-δ)-approximate polynomial time algorithm for the (1,ε)-restricted assignment problem for a fixed constant δ > 0. Even for this special case, the best polynomial-time approximation factor known so far is 2. We obtain this result by rounding the configuration LP relaxation for this problem. A simple reduction from vertex cover shows that this special case remains NP-hard to approximate to within a factor better than 7/6.
- Approximating k-Median via Pseudo-Approximation (arxiv)[Abstract]
S. Li and Ola Svensson
STOC 2013
We present a novel approximation algorithm for k-median that achieves an approximation guarantee of 1+sqrt(3)+ε, improving upon the decade-old ratio of 3+ε. Our approach is based on two components, each of which, we believe, is of independent interest. First, we show that in order to give an α-approximation algorithm for k-median, it is sufficient to give a pseudo-approximation algorithm that finds an α-approximate solution by opening k + O(1) facilities. This is a rather surprising result as there exist instances for which opening k + 1 facilities may lead to a significant smaller cost than if only k facilities were opened.
Second, we give such a pseudo-approximation algorithm with α=1+sqrt(3)+ε. Prior to our work, it was not even known whether opening k + o(k) facilities would help improve the approximation ratio.
- A Polylogarithmic Approximation for Edge-Disjoint-Paths with Congestion 2 (arxiv)[Abstract]
Julia Chuzhoy and S. Li
FOCS 2012
co-winner of best paper award
In the Edge-Disjoint Paths with Congestion problem (EDPwC), we are given an undirected n-vertex graph G, a collection M={(s1,t1), ... ,(sk,tk)} of demand pairs and an integer c. The goal is to connect the maximum possible number of the demand pairs by paths, so that the maximum edge congestion - the number of paths sharing any edge - is bounded by c. When the maximum allowed congestion is c=1, this is the classical Edge-Disjoint Paths problem (EDP).
The best current approximation algorithm for EDP achieves an O(sqrt(n))-approximation, by rounding the standard multi-commodity flow relaxation of the problem. This matches the Ω(sqrt n) lower bound on the integrality gap of this relaxation. We show an O(polylog k)-approximation algorithm for EDPwC with congestion c=2, by rounding the same multi-commodity flow relaxation. This gives the best possible congestion for a sub-polynomial approximation of EDPwC via this relaxation. Our results are also close to optimal in terms of the number of pairs routed, since EDPwC is known to be hard to approximate to within a factor of tildeΩ(log n)1/(c+1)) for any constant congestion c. Prior to our work, the best approximation factor for EDPwC with congestion 2 was tildeO(n3/7), and the best algorithm achieving a polylogarithmic approximation required congestion 14.
- A 1.488-Approximation Algorithm for the Uncapacitated Facility Location Problem [Abstract]
S. Li
ICALP 2011
best student paper of Track A
We present a 1.488 approximation algorithm for the metric uncapacitated facility location (UFL) problem. Previously the best algorithm was due to Byrka. By linearly combining two algorithms A1(γf) for γf approx 1.6774 and the (1.11,1.78)-approximation algorithm A2 proposed by Jain, Mahdian and Saberi, Byrka gave a 1.5 approximation algorithm for the UFL problem. We show that if γf is randomly selected from some distribution, the approximation ratio can be improved to 1.488. Our algorithm cuts the gap with the 1.463 approximability lower bound by almost 1/3.
Teaching
PhD Advisees
- Xiangyu Guo
- Yunus Esencayi (co-advising with Prof. Roger He)
- Jiayi Xian (co-advising with Prof. Jinhui Xu)
- Alexander Stachnik
Professional Activities
PC member for APPROX+RANDOM 2017, SWAT 2018, MAPSP 2019 (upcoming)
