Shi Li's Home Page

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. Currently, I am especially interested in the use of LP/SDP hierarchies in tackling these problems.

My research is supported by NSF grant CCF-1566356 (CRII), CCF-1717134 and CCF-1844890 (Career Award).

Teaching

• Fall 2019 (current semester): CSE632: Analysis of Algorithms II : Randomized Algorithms
• Fall 2019 (current semester): CSE 730 Seminar : Data Structures and Algorithms in Solving Programming Problems
• CSE431/531: Analysis of Algorithms I (Spring 2019, Spring 2018, Fall 2016, Spring 2016)
• CSE711: Topics in Combinatorial Optimization and Linear Programming (Seminar) (Fall 2018)
• CSE 632: Analysis of Algorithms II : Approximation Algorithms (Fall 2017)
• CSE712: Advanced Topics in Algorithm Design (Seminar) (Fall 2015)
• EECS336: Design and Analysis of Algorithms (Winter 2015) at Northwestern University
• co-teaching Information and Coding Theory (Fall 2014) at TTIC with Madhur Tulsiani

PhD Advisees

• Xiangyu Guo
• Yunus Esencayi (co-advising with Prof. Roger He)
• Jiayi Xian (co-advising with Prof. Jinhui Xu)
• Alexander Stachnik

Publications

Below is a sampled list of my publications. Full list of my publications.

• O(log²k/loglog k)-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm (arXiv)[Abstract]
      Fabrizio Grandoni, Bundit Laekhanukit and S. Li
      STOC 2019
  

  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(log² k / log log k)-approximation algorithm for DST that runs in quasi-polynomial-time, i.e., in time n^{polylog k}. With standard complexity assumptions, we show a matching lower bound of Ω(log²k / 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(log³ k) approximation algorithm by Charikar et al. [SODA'98 & J. Algorithms'99]. (The paper erroneously claims an O(log²k) 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.

• Topology Dependent Bounds for (Some) FAQs
      Michael Langberg, S. Li, Sai Vikneshwar Mani Jayaraman and Atri Rudra
      PODS 2019
  
• Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time [Abstract]
      Shashwat Garg, Janardhan Kulkarni and S. Li
      SODA 2019
  

  We consider the classic problem of scheduling jobs with precedence constraints on a set of identical machines to minimize the weighted completion time objective. Understanding the exact approximability of the problem when job lengths are uniform is a well known open problem in scheduling theory. In this paper, we show an optimal algorithm that runs in polynomial time and achieves an approximation factor of (2 + ε) for the weighted completion time objective when the number of machines is a constant. The result is obtained by building on the lift and project approach introduced in a breakthrough work by Levey and Rothvoss for the makespan minimization problem.

• 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 r_j, a processing time p_j, and a weight w_j. The flow-time of a job is defined as the amount of time the job spends in the system before it completes; that is, F_j = C_j - r_j, where C_j 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 (arXiv)[Abstract]
      Xiangyu Guo and S. Li
      NeurIPS 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 (α₁ + ε ≈ 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 (α₂ + ε ≈ 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 α₁- and (α₁ + ε)-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 (p_j = 1) or light (p_j = ε), 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={(s₁,t₁), ... ,(s_k,t_k)} 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(n^3/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.

Professional Activities

• PC member for APPROX+RANDOM 2017, SWAT 2018, MAPSP 2019, ISAAC 2019, TAMC 2020 (upcoming)
• Editorial Board Member of the ACM Transactions on Algorithms (since March 2019)
• Guest Editor of A Special Issue of Journal of Scheduling
• Local Committee Member of FWCG 2015