Shi Li 0001

SODA Conference 2025 Conference Paper

Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs

• Shi Li 0001

STOC Conference 2025 Conference Paper

Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations

• Yuda Feng
• Yang Hu
• Shi Li 0001
• Ruilong Zhang 0001

We study the problem of assigning items to agents so as to maximize the weighted Nash Social Welfare (NSW) under submodular valuations. The best-known result for the problem is an O ( nw max )-approximation due to Garg, Husic, Li, Vegh, and Vondrak (STOC’23), where w max is the maximum weight over all agents. Obtaining a constant approximation algorithm is an open problem in the field that has recently attracted considerable attention. We give the first such algorithm for the problem, thus solving the open problem in the affirmative. Our algorithm is based on the natural Configuration LP for the problem, which was introduced recently by Feng and Li (ICALP’24) for the additive valuation case. Our rounding algorithm is similar to that of Li (SODA’25) developed for the unrelated machine scheduling problem to minimize weighted completion time. Roughly speaking, we designate the largest item in each configuration as a large item and the remaining items as small items. So, every agent gets precisely 1 fractional large item in the configuration LP solution. With the rounding algorithm in Li (SODA’25), we can ensure that in the obtained solution, every agent gets precisely 1 large item, and the assignments of small items are negatively correlated.

STOC Conference 2025 Conference Paper

Solving the Correlation Cluster LP in Sublinear Time

• Nairen Cao
• Vincent Cohen-Addad
• Euiwoong Lee
• Shi Li 0001
• David Rasmussen Lolck
• Alantha Newman
• Mikkel Thorup
• Lukas Vogl

Correlation Clustering is a fundamental and widely-studied problem in unsupervised learning and data mining. The input is a graph and the goal is to construct a clustering minimizing the number of inter-cluster edges plus the number of missing intra-cluster edges. Cao, Cohen-Addad, Lee, Li, Newman, and Vogl [STOC 2024] introduced the cluster LP for Correlation Clustering, which they argued captures the problem much more succinctly than previous linear programming formulations. However, the cluster LP has exponential size, with a variable for every possible set of vertices in the input graph. Nevertheless, they showed how to find a feasible solution for the cluster LP in time O ( n poly(1/ε) ) with objective value at most (1+ε) times the value of an optimal solution for the respective Correlation Clustering instance. Furthermore, they showed how to round a solution to the cluster LP, yielding a (1.437+ε)-approximation algorithm for the Correlation Clustering problem. The main technical result of this paper is a new approach to find a feasible solution for the cluster LP with objective value at most (1+ε) of the optimum in time O (2 poly(1/ε) n ), where n is the number of vertices in the graph. We also show how to implement the rounding within the same time bounds, thus achieving a fast (1.437+ε)-approximation algorithm for the Correlation Clustering problem. This bridges the gap between state-of-the-art methods for approximating Correlation Clustering and the recent focus on fast algorithms.

STOC Conference 2024 Conference Paper

Understanding the Cluster Linear Program for Correlation Clustering

• Nairen Cao
• Vincent Cohen-Addad
• Euiwoong Lee
• Shi Li 0001
• Alantha Newman
• Lukas Vogl

In the classic Correlation Clustering problem introduced by Bansal, Blum, and Chawla ‍(FOCS 2002), the input is a complete graph where edges are labeled either + or −, and the goal is to find a partition of the vertices that minimizes the sum of the +edges across parts plus the sum of the -edges within parts. In recent years, Chawla, Makarychev, Schramm and Yaroslavtsev ‍(STOC 2015) gave a 2.06-approximation by providing a near-optimal rounding of the standard LP, and Cohen-Addad, Lee, Li, and Newman ‍(FOCS 2022, 2023) finally bypassed the integrality gap of 2 for this LP giving a 1.73-approximation for the problem. While introducing new ideas for Correlation Clustering, their algorithm is more complicated than typical approximation algorithms in the following two aspects: (1) It is based on two different relaxations with separate rounding algorithms connected by the round-or-cut procedure. (2) Each of the rounding algorithms has to separately handle seemingly inevitable correlated rounding errors , coming from correlated rounding of Sherali-Adams and other strong LP relaxations. In order to create a simple and unified framework for Correlation Clustering similar to those for typical approximate optimization tasks, we propose the cluster LP as a strong linear program that might tightly capture the approximability of Correlation Clustering. It unifies all the previous relaxations for the problem. It is exponential-sized, but we show that it can be (1+є)-approximately solved in polynomial time for any є > 0, providing the framework for designing rounding algorithms without worrying about correlated rounding errors; these errors are handled uniformly in solving the relaxation. We demonstrate the power of the cluster LP by presenting a simple rounding algorithm, and providing two analyses, one analytically proving a 1.49-approximation and the other solving a factor-revealing SDP to show a 1.437-approximation. Both proofs introduce principled methods by which to analyze the performance of the algorithm, resulting in a significantly improved approximation guarantee. Finally, we prove an integrality gap of 4/3 for the cluster LP, showing our 1.437-upper bound cannot be drastically improved. Our gap instance directly inspires an improved NP-hardness of approximation with a ratio 24/23 ≈ 1.042; no explicit hardness ratio was known before.

FOCS Conference 2023 Conference Paper

Handling Correlated Rounding Error via Preclustering: A 1. 73-approximation for Correlation Clustering

• Vincent Cohen-Addad
• Euiwoong Lee
• Shi Li 0001
• Alantha Newman

We consider the classic correlation clustering problem: Given a complete graph where edges are labelled either + or −, the goal is to find a partition of the vertices that minimizes the sum of the +edges across parts plus the sum of the −edges within parts. Recently, Cohen-Addad, Lee and Newman [CLN22] gave a 1. 995-approximation for the problem using the Sherali-Adams hierarchy, hence beating the integrality gap of 2 of the classic linear program. We significantly improve upon this result by providing a 1. 73-approximation for the problem. Our approach brings together a new preprocessing of correlation clustering instances that enables a new LP formulation which combined with the algorithm from [CLN22] yields the improved bound.

SODA Conference 2023 Conference Paper

Improved Approximations for Unrelated Machine Scheduling

• Sungjin Im
• Shi Li 0001

We revisit two well-studied scheduling problems in the unrelated machines setting where each job can have a different processing time on each machine. For minimizing total weighted completion time we give a 1. 45-approximation, which improves upon the previous 1. 488-approximation [Im and Shadloo SODA 2020]. The key technical ingredient in this improvement lies in a new rounding scheme that gives strong negative correlation with less restrictions. For minimizing L k -norms of machine loads, inspired by [Kalaitzis et al. SODA 2017], we give better approximation algorithms. In particular we give a -approximation for the L 2 -norm which improves upon the former -approximations due to [Azar-Epstein STOC 2005] and [Kumar et al. JACM 2009].

STOC Conference 2023 Conference Paper

Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse

• Ravishankar Krishnaswamy
• Shi Li 0001
• Varun Suriyanarayana

SODA Conference 2022 Conference Paper

Polynomial Integrality Gap of Flow LP for Directed Steiner Tree

• Shi Li 0001
• Bundit Laekhanukit

In the Directed Steiner Tree (DST) problem, we are given a directed graph G = (V, E ) on n vertices with edge-costs, a root vertex r, and a set K of k terminals. The goal is to find a minimum-cost subgraph of G that contains a path from r to every terminal t ∊ k. DST has been a notorious problem for decades as there is a large gap between the best-known polynomial-time approximation ratio of O ( k∊ ) for any constant ∊ > 0, and the best quasi-polynomial-time approximation ratio of. Towards understanding this gap, we study the integrality gap of the standard flow LP relaxation for the problem. We show that the LP has an integrality gap polynomial in n. Previously, the integrality gap LP is only known to be [Halperin et al. , SODA'03 & SIAM J. Comput. ] and [Zosin-Khuller, SODA'02] in some instance with. Our result gives the first known lower bound on the integrality gap of this standard LP that is polynomial in n, the number of vertices. Consequently, we rule out the possibility of developing a poly-logarithmic approximation algorithm for the problem based on the flow LP relaxation.

ICML Conference 2021 Conference Paper

Online Unrelated Machine Load Balancing with Predictions Revisited

• Shi Li 0001
• Jiayi Xian

We study the online load balancing problem with machine learned predictions, and give results that improve upon and extend those in a recent paper by Lattanzi et al. (2020). First, we design deterministic and randomized online rounding algorithms for the problem in the unrelated machine setting, with $O(\frac{\log m}{\log \log m})$- and $O(\frac{\log \log m}{\log \log \log m})$-competitive ratios. They respectively improve upon the previous ratios of $O(\log m)$ and $O(\log^3\log m)$, and match the lower bounds given by Lattanzi et al. Second, we extend their prediction scheme from the identical machine restricted assignment setting to the unrelated machine setting. With the knowledge of two vectors over machines, a dual vector and a weight vector, we can construct a good fractional assignment online, that can be passed to an online rounding algorithm. Finally, we consider the learning model introduced by Lavastida et al. (2020), and show that under the model, the two vectors can be learned efficiently with a few samples of instances.

SODA Conference 2021 Conference Paper

Towards PTAS for Precedence Constrained Scheduling via Combinatorial Algorithms

• Shi Li 0001

We study the classic problem of scheduling n precedence constrained unit-size jobs on m = O (1) machines so as to minimize the makespan. In a recent breakthrough, Levey and Rothvoss [11] developed a (1 +∊)-approximation for the problem with running time, via the Sherali-Adams lift of the basic linear programming relaxation for the problem by levels. Garg [6] recently improved the number of levels to, and thus the running time to, which is quasi-polynomial for constant m and ∊. In this paper we present a (1 + ∊)-approximation algorithm for the problem with running time, which is very close to a polynomial for constant m and ∊. Unlike the algorithms of Levey-Rothvoss and Garg, which are based on the linear-programming hierarchy, our algorithm is purely combinatorial. We show that the conditioning operations on the lifted LP solution can be replaced by making guesses about the optimum schedule. Compared to the LP hierarchy framework, our guessing framework has two advantages, both playing important roles in deriving the improved running time. First, we can guess any information about the optimum schedule, as long as it can be described using a few bits, while in the conditioning framework, we can only condition on the variables in the basic LP. Second, the guessing framework can save a factor of log n in the exponent of running time. Roughly speaking, most of the time, the information we try to guess is binary and thus each nested guess only contributes to a multiplicative factor of 2 in the running time. In contrast, each conditioning operation in a sequence incurs a multiplicative factor of poly( n ).

SODA Conference 2020 Conference Paper

Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints

• Janardhan Kulkarni
• Shi Li 0001
• Jakub Tarnawski
• Minwei Ye

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 approximability of the problem when the number of machines is a constant is a well-known question in scheduling theory. Indeed, an outstanding open problem from the classic book of Garey and Johnson [9] asks whether this problem is NP-hard even in the case of 3 machines and unit-length jobs. In a recent breakthrough, Levey and Rothvoss [24] gave a (1 + ϵ )-approximation algorithm, which runs in nearly quasi-polynomial time, for the case when job have unit lengths. However, a substantially more difficult case where jobs have arbitrary processing lengths has remained open. We make progress on this more general problem. We show that there exists a (1 + ϵ )-approximation algorithm (with similar running time as that of [24]) for the nonmigratory setting: when every job has to be scheduled entirely on a single machine, but within a machine the job need not be scheduled during consecutive time steps. Further, we also show that our algorithmic framework generalizes to another classic scenario where, along with the precedence constraints, the jobs also have communication delay constraints. Both of these fundamental problems are highly relevant to the practice of datacenter scheduling.

SODA Conference 2019 Conference Paper

A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time

• Uriel Feige
• Janardhan Kulkarni
• Shi Li 0001

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 [6] 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 [6] settles the long standing conjecture that there is a polynomial time algorithm with O (1)-approximation for min-WPFT.

SODA Conference 2019 Conference Paper

Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time

• Shashwat Garg
• Janardhan Kulkarni
• Shi Li 0001

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 [15] for the makespan minimization problem.

STOC Conference 2019 Conference Paper

O (log 2 k / log log k )-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm

• Fabrizio Grandoni 0001
• Bundit Laekhanukit
• Shi Li 0001

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 subgraph that contains a directed path from r to every terminal. We present an O(log^2 k /log log k )-approximation algorithm for DST that runs in quasi-polynomial-time, i.e., in time n^polylog(k). By making standard complexity assumptions, we show the matching lower bound of Omega(log^2 k/loglogk) 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^3 k ) approximation algorithm by Charikar et al. [SODA’98J. Algorithms’99]. (The paper erroneously claims an O (log^2 k ) approximation due to a mistake in prior work.)

SODA Conference 2019 Conference Paper

On Facility Location with General Lower Bounds

• Shi Li 0001

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 [27] gave a 448-approximation for the special case, and subsequently Ahmadian and Swamy [2] improved the approximation factor to 82. 6. As in [27] and [2], 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.

STOC Conference 2018 Conference Paper

Constant approximation for k-median and k-means with outliers via iterative rounding

• Ravishankar Krishnaswamy
• Shi Li 0001
• Sai Sandeep

In this paper, we present a new iterative rounding framework for many clustering problems. Using this, we obtain an (α 1 + є ≤ 7.081 + є)-approximation algorithm for k -median with outliers, greatly improving upon the large implicit constant approximation ratio of Chen. For k -means with outliers, we give an (α 2 +є ≤ 53.002 + є)-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 and knapsack median problems respectively, improving upon the previous best approximations ratios of 8 due to Swamy and 17.46 due to Byrka et al. 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.

SODA Conference 2017 Conference Paper

Constant Approximation Algorithm for Non-Uniform Capacitated Multi-Item Lot-Sizing via Strong Covering Inequalities

• Shi Li 0001

FOCS Conference 2017 Conference Paper

Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations

• Shi Li 0001

We study approximation algorithms for scheduling problems with the objective of minimizing total weighted completion time, under identical and related machine models with job precedence constraints. We give algorithms that improve upon many 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 relaxations for their respective problems, but surprisingly are not studied 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 this relaxation can provide new insights into the problem.

SODA Conference 2017 Conference Paper

Tight Network Topology Dependent Bounds on Rounds of Communication

• Arkadev Chattopadhyay
• Michael Langberg
• Shi Li 0001
• Atri Rudra

We prove tight network topology dependent bounds on the round complexity of computing well studied k -party functions such as set disjointness and element distinctness. Unlike the usual case in the CONGEST model in distributed computing, we fix the function and then vary the underlying network topology. This complements the recent such results on total communication that have received some attention. We also present some applications to distributed graph computation problems. Our main contribution is a proof technique that allows us to reduce the problem on a general graph topology to a relevant two-party communication complexity problem. However, unlike many previous works that also used the same high level strategy, we do not reason about a two-party communication problem that is induced by a cut in the graph. To ‘stitch’ back the various lower bounds from the two party communication problems, we use the notion of timed graph that has seen prior use in network coding. Our reductions use some tools from Steiner tree packing and multi-commodity flow problems that have a delay constraint.

SODA Conference 2016 Conference Paper

Approximating capacitated k -median with (1 + ∊) k open facilities

• Shi Li 0001

In the capacitated k -median (CKM) problem, we are given a set F of facilities, each facility i ∊ F with a capacity u i, a set C of clients, a metric d over F ∪ C and an integer k. The goal is to open k facilities in F and connect the clients C to the open facilities such that each facility i is connected by at most u i clients, so as to minimize the total connection cost. In this paper, we give the first constant approximation for CKM, that only violates the cardinality constraint by a factor of 1 + ∊. This generalizes the result of [Li15], which only works for the uniform capacitated case. Moreover, the approximation ratio we obtain is, which is an exponential improvement over the ratio of in [Li15]. The natural LP relaxation for the problem, which almost all previous algorithms for CKM are based on, has unbounded integrality gap even if (2 – ∊ ) k facilities can be opened. We introduce a novel configuration LP for the problem, that overcomes this integrality gap. On the downside, each facility may be opened twice by our algorithm.

FOCS Conference 2016 Conference Paper

Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-uniform Distributions

• Sungjin Im
• Shi Li 0001

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 | Σ j w j C j using the three-field notation. For this problem, a 2-approximation is known based on a novel convex programming (J. ACM 2001 by Skutella). It has been a long standing open problem if one can improve upon this 2-approximation (Open Problem 8 in J. of Sched. 1999 by Schuurman and Woeginger). We answer this question in the affirmative by giving a 1. 8786-approximation. We achieve this via a surprisingly simple linear programming, but a novel rounding algorithm and analysis. A key ingredient of our algorithm is the use of random offsets sampled from non-uniform distributions. We also consider the preemptive version of the problem, i. e, R|r ij, pmtn|Σ j w j C j. We again use the idea of sampling offsets from non-uniform distributions to give the first better than 2-approximation for this problem. This improvement also requires use of a configuration LP with variables for each job's complete schedules along with more careful analysis. For both non-preemptive and preemptive versions, we break the approximation barrier of 2 for the first time.

STOC Conference 2016 Conference Paper

Improved approximation for node-disjoint paths in planar graphs

• Julia Chuzhoy
• David H. K. Kim
• Shi Li 0001

We study the classical Node-Disjoint Paths (NDP) problem: given an n -vertex graph G and a collection =( s 1 , t 1 ),…,( s k , t k ) of pairs of vertices of G called demand pairs , find a maximum-cardinality set of node-disjoint paths connecting the demand pairs. NDP is one of the most basic routing problems, that has been studied extensively. Despite this, there are still wide gaps in our understanding of its approximability: the best currently known upper bound of O (√ n ) on its approximation ratio is achieved via a simple greedy algorithm, while the best current negative result shows that the problem does not have a better than Ω(log 1/2−δ n )-approximation for any constant δ, under standard complexity assumptions. Even for planar graphs no better approximation algorithms are known, and to the best of our knowledge, the best negative bound is APX-hardness. Perhaps the biggest obstacle to obtaining better approximation algorithms for NDP is that most currently known approximation algorithms for this type of problems rely on the standard multicommodity flow relaxation, whose integrality gap is Ω(√ n ) for NDP, even in planar graphs. In this paper, we break the barrier of O (√ n ) on the approximability of NDP in planar graphs and obtain an Õ( n 9/19 )-approximation. We introduce a new linear programming relaxation of the problem, and a number of new techniques, that we hope will be helpful in designing more powerful algorithms for this and related problems.

SODA Conference 2015 Conference Paper

A Dynamic Programming Framework for Non-Preemptive Scheduling Problems on Multiple Machines [Extended Abstract]

• Sungjin Im
• Shi Li 0001
• Benjamin Moseley
• Eric Torng

In this paper, we consider a variety of scheduling problems where n jobs with release times are to be scheduled non-preemptively on a set of m identical machines. The problems considered are machine minimization, (weighted) throughput maximization and min-sum objectives such as (weighted) flow time and (weighted) tardiness. We develop a novel quasi-polynomial time dynamic programming framework that gives O (l)-speed O (l)-approximation algorithms for the offline versions of machine minimization and min-sum problems. For the weighted throughput problem, the framework gives a (1 + ε)-speed (1 – ε)-approximation algorithm. The generic DP is based on improving a naïve exponential time DP by developing a sketching scheme that compactly and accurately approximates parameters used in the DP states. We show that the loss of information due to the sketching scheme can be offset with limited resource augmentation. This framework is powerful and flexible, allowing us to apply it to this wide range of scheduling objectives and settings. We also provide new insight into the relative power of speed augmentation versus machine augmentation for non-preemptive scheduling problems; specifically, we give new evidence for the power and importance of extra speed for some non-preemptive scheduling problems. This novel DP framework leads to many new algorithms with improved results that solve many open problems, albeit with quasi-polynomial running times. We highlight our results as follows. For the problems with min-sum objectives, we give the first O (l)-speed O (l)-approximation algorithms for the multiple-machine setting. Even for the single machine case, we reduce both the resource augmentation required and the approximation ratios. In particular, our approximation ratios are either 1 or 1 + ε. Most of our algorithms use speed 1 + e or 2 + ε. We also resolve an open question (albeit with a quasi-polynomial time algorithm) of whether less than 2-speed could be used to achieve an O (1)-approximation for flow time. New techniques are needed to address this open question since it was proven that previous techniques are insufficient. We answer this open question by giving an algorithm that achieves a (1 + ε)-speed 1-approximation for flow time and (1 + ε)-speed (1 + ε)-approximation for weighted flow time. For the machine minimization problem, we give the first result using constant resource augmentation by showing a (1 + ε)-speed 2-approximation, and the first result only using speed augmentation and no additional machines by showing a (2 + ε)-speed 1-approximation. We complement our positive results for machine minimization by considering the discrete variant of the problem and show that no algorithm can use speed augmentation less than 2 log 1–ε and achieve approximation less than O (log log n ) for any constant ε > 0 unless NP admits quasi-polynomial time optimal algorithms. Thus, our results show a stark contrast between the two settings. In one, constant speed augmentation is sufficient whereas in the other, speed augmentation is essentially not effective.

SODA Conference 2015 Conference Paper

On (1, ∊ )-Restricted Assignment Makespan Minimization

• Deeparnab Chakrabarty
• Sanjeev Khanna
• Shi Li 0001

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 [16] 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.

SODA Conference 2015 Conference Paper

On Uniform Capacitated k -Median Beyond the Natural LP Relaxation

• Shi Li 0001

In this paper, we study the uniform capacitated k- median problem. In the problem, we are given a set ℱ of potential facility locations, a set of clients, a metric d over ℱ ∪, an upper bound k on the number of facilities we can open and an upper bound u on the number of clients each facility can serve. We need to open a subset ⊆ ℱ of k facilities and connect clients in to facilities in so that each facility is connected by at most u clients. The goal is to minimize the total connection cost over all clients. Obtaining a constant approximation algorithm for this problem is a notorious open problem; most previous works gave constant approximations by either violating the capacity constraints or the cardinality constraint. Notably, all these algorithms are based on the natural LP-relaxation for the problem. The LP-relaxation has unbounded integrality gap, even when we are allowed to violate the capacity constraints or the cardinality constraint by a factor of 2 — ε. Our result is an exp( O (1/ε 2 ))-approximation algorithm for the problem that violates the cardinality constraint by a factor of 1 + ε. That is, we find a solution that opens at most (1 + ε) k facilities whose cost is at most exp( O (1/ε 2 )) times the optimum solution when at most k facilities can be open. This is already beyond the capability of the natural LP relaxation, as it has unbounded integrality gap even if we are allowed to open (2 — ε) k facilities. Indeed, our result is based on a novel LP for this problem. We hope that this LP is the first step towards a constant approximation for capacitated k -median. The version as we described is the hard-capacitated version of the problem, as we can only open one facility at each location. This is as opposed to the soft-capacitated version, in which we are allowed to open more than one facilities at each location. The hard-capacitated version is more general, since one can convert a soft-capacitated instance to a hard-capacitated instance by making enough copies of each facility location. We give a simple proof that in the uniform capacitated case, the soft-capacitated version and the hard-capacitated version are actually equivalent, up to a small constant loss in the approximation ratio. Moreover, we show that the given potential facility locations do not matter: we can assume ℱ =.

SODA Conference 2014 Conference Paper

A Constant Factor Approximation Algorithm for Fault-Tolerant k -Median

• MohammadTaghi Hajiaghayi
• Wei Hu
• Jian Li 0015
• Shi Li 0001
• Barna Saha

In this paper, we consider the fault-tolerant k -median problem and give the first constant factor approximation algorithm for it. In the fault-tolerant generalization of classical k -median problem, each client j needs to be assigned to at least r j ≥ 1 distinct open facilities. The service cost of j is the sum of its distances to the r j facilities, and the k -median constraint restricts the number of open facilities to at most k. Previously, a constant factor was known only for the special case when all r j s are the same, and a logarithmic approximation ratio was known for the general case. In addition, we present the first polynomial time algorithm for the fault-tolerant k -median problem on a path or a HST by showing that the corresponding LP always has an integral optimal solution. We also consider the fault-tolerant facility location problem, where the service cost of j can be a weighted sum of its distance to the r j facilities. We give a simple constant factor approximation algorithm, generalizing several previous results which only work for nonincreasing weight vectors.

SODA Conference 2014 Conference Paper

Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach

• Nikhil Bansal 0001
• Moses Charikar
• Ravishankar Krishnaswamy
• Shi Li 0001

We study the broadcast scheduling problem with the objective of minimizing the average response time. There is a single server that can hold n pages of unit size, and multiple requests for these pages arrive over time. At each time slot the server can broadcast one page which satisfies all the outstanding requests for this page at that time. The goal is to find a schedule to minimize the average response time of the requests, i. e. the duration since a request arrives until it is satisfied. We give an Õ (log 1, 5 n ) approximation algorithm for the problem improving upon the previous Õ (log 2 n ) approximation. We also show an Ω(log 1/2–∊ n ) hardness result, and an integrality gap of Ω(log n ) for the natural LP relaxation for the problem. Prior to our work, only NP-Hardness and a (tiny) constant integrality gap was known. These results are based on establishing a close connection to the discrepancy minimization problem for permutation set-systems. Specifically, our improved approximation is based on using recent algorithmic ideas developed for discrepancy minimization. Our integrality gap is obtained from the Ω(log n )-lower bound on the discrepancy of 3-permutations, while our hardness result is based on establishing the first hardness result for the discrepancy of ℓ -permutations.

STOC Conference 2013 Conference Paper

Approximating k-median via pseudo-approximation

• Shi Li 0001
• Ola Svensson

We present a novel approximation algorithm for k-median that achieves an approximation guarantee of 1+√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.

FOCS Conference 2012 Conference Paper

A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2

• Julia Chuzhoy
• Shi Li 0001

In the Edge-Disjoint Paths with Congestion problem (EDPwC), we are given an undirected n-vertex graph G, a collection M = {(s 1, t 1 ), .. ., (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(√n)-approximation, by rounding the standard multicommodity How relaxation of the problem. This matches the Ω(√n) lower bound on the integrality gap of this relaxation. We show an O(poly log k)-approximation algorithm for EDPwC with congestion c = 2, by rounding the same multi-commodity How 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 Ω̅(log n) 1/(c+1) ) for any constant congestion c. Prior to our work, the best approximation factor for EDPwC with congestion 2 was O̅(n 3/7 ), and the best algorithm achieving a polylogarithmic approximation required congestion 14.

STOC Conference 2012 Conference Paper

Approximation algorithms and hardness of integral concurrent flow

• Parinya Chalermsook
• Julia Chuzhoy
• Alina Ene
• Shi Li 0001

We study an integral counterpart of the classical Maximum Concurrent Flow problem, that we call Integral Concurrent Flow (ICF). In the basic version of this problem (basic-ICF), we are given an undirected n-vertex graph $G$ with edge capacities c(e), a subset T of vertices called terminals, and a demand D(t,t') for every pair (t,t') of the terminals. The goal is to find a maximum value λ, and a collection P of paths, such that every pair (t,t') of terminals is connected by ⌊ λ ⋅ D(t,t')⌋ paths in P, and the number of paths containing any edge e is at most c(e). We show an algorithm that achieves a poly log n-approximation for basic-ICF, while violating the edge capacities by only a constant factor. We complement this result by proving that no efficient algorithm can achieve a factor α-approximation with congestion c for any values α,c satisfying α ⋅ c=O(log log n/log log log n), unless NP ⊆ ZPTIME(n poly log n ). We then turn to study the more general group version of the problem (group=ICF), in which we are given a collection (S 1 ,T 1 ),...,(S k ,T k )} of pairs of vertex subsets, and for each 1 ≤ i ≤ k, a demand D i is specified. The goal is to find a maximum value λ and a collection P of paths, such that for each i, at least ⌊ λ ⋅ D i ⌋ paths connect the vertices of S i to the vertices of T i , while respecting the edge capacities. We show that for any 1 ≤ c ≤ O(log log n), no efficient algorithm can achieve a factor O(n 1/(2 2c+3 ) )-approximation with congestion c for the problem, unless NP ⊆ DTIME(n O(log log n) ). On the other hand, we show an efficient randomized algorithm that finds a poly log n-approximate solution with a constant congestion, if we are guaranteed that the optimal solution contains at least D ≥ k poly log n paths connecting every pair (S i ,T i ).

FOCS Conference 2010 Conference Paper

Vertex Sparsifiers and Abstract Rounding Algorithms

• Moses Charikar
• Frank Thomson Leighton
• Shi Li 0001
• Ankur Moitra

The notion of vertex sparsification (in particular cut-sparsification) is introduced in, where it was shown that for any graph G = (V, E) and any subset of k terminals K ⊂ V, there is a polynomial time algorithm to construct a graph H = (K, E H ) on just the terminal set so that simultaneously for all cuts (A, K-A), the value of the minimum cut in G separating A from K-A is approximately the same as the value of the corresponding cut in H. Then approximation algorithms can be run directly on H as a proxy for running on G. We give the first super-constant lower bounds for how well a cut-sparsifier H can simultaneously approximate all minimum cuts in G. We prove a lower bound of Ω(log 1/4 k) this is polynomially-related to the known upper bound of O(log k/log log k). Independently, a similar lower bound is given in. This is an exponential improvement on the Ω(log log k) bound given in which in fact was for a stronger vertex sparsification guarantee, and did not apply to cut sparsifiers. Despite this negative result, we show that for many natural optimization problems, we do not need to incur a multiplicative penalty for our reduction. Roughly, we show that any rounding algorithm which also works for the O-extension relaxation can be used to construct good vertex-sparsifiers for which the optimization problem is easy. Using this, we obtain optimal O(log k)-competitive Steiner oblivious routing schemes, which generalize the results in. We also demonstrate that for a wide range of graph packing problems (which includes maximum concurrent flow, maximum multiflow and multicast routing, among others, as a special case), the integrality gap of the linear program is always at most O(log k) times the integrality gap restricted to trees. Lastly, we use our ideas to give an efficient construction for vertex-sparsifiers that match the current best existential results - this was previously open. Our algorithm makes novel use of Earth-mover constraints.