Correlation clustering is a well-studied problem, first proposed by Bansal, Blum, and Chawla [Mach. Learn. '04]. The input is an unweighted, undirected graph. The problem is to cluster the vertices so as to minimize the number of edges between vertices in different clusters and missing edges between vertices inside the same cluster. This problem has a wide application in data mining and machine learning. We introduce a general framework that transforms existing static correlation clustering algorithms into fully-dynamic ones that work against an adaptive adversary. We show how to apply our framework to known efficient correlation clustering algorithms, starting from the classic 3-approximate Pivot algorithm from Ailon, Charikar and Newman [JACM'08]. Applied to the most recent sublinear $1.485$-approximation algorithm from Cao, Cohen-Addad, Lee, Li, Lolck, Newman, Thorup, Vogl, Yan and Zhang [STOC'25], we get a $1.485$-approximation fully-dynamic algorithm that works with worst-case constant update time. The original static algorithm gets its approximation factor with constant probability, and we get the same against an adaptive adversary in the sense that for any given update step, not known to our algorithm, our solution is a $1.485$-approximation with constant probability when we reach this update. Most of previous dynamic algorithms, including the celebrated result from Behnezhad, Charikar, Ma and Tan [FOCS'19], had approximation factors around $3$ in expectation, and they could only handle an oblivious adversary. A recent algorithm by Braverman, Dharangutte, Pai, Shah, and Wang [AISTATS'25] could handle an adaptive adversary, but it has a large unspecified constant approximation ratio. This contrasts with our general transformation, which works with all the best approximation factors known for the static case.

Following recent advances in combining approximation algorithms with fixed-parameter tractability (FPT), we study FPT-time approximation algorithms for minimum-norm k-clustering problems, parameterized by the number k of open facilities. For the capacitated setting, we give a tight (3+ε)-approximation for the general-norm capacitated k-clustering problem in FPT-time parameterized by k and ε. Prior to our work, such a result was only known for the capacitated k-median problem [Cohen-Addad and Li, 2019]. As a special case, our result yields an FPT-time 3-approximation for capacitated k-center. The problem has not been studied in the FPT-time setting, with the previous best known polynomial-time approximation ratio being 9 [An et al., 2015]. In the uncapacitated setting, we consider the top-cn norm k-clustering problem, where the goal of the problem is to minimize the top-cn norm of the connection distance vector. Our main result is a tight (1 + 2/(ec) + ε)-approximation algorithm for the problem with c ∈ (1/e, 1]. (For the case c ≤ 1/e, there is a simple tight (3+ε)-approximation.) Our framework can be easily extended to give a tight (3, 1 + 2/e + ε)-bi-criteria approximation for the (k-center, k-median) problem in FPT time, improving the previous best polynomial-time (4, 8) guarantee [Soroush Alamdari and David B. Shmoys, 2017]. All results are based on a unified framework: computing a (1+ε)-approximate solution using O((k log n)/ε) facilities S via LP rounding, sampling a few client representatives R based on the solution S, guessing a few pivots from S ∪ R and some radius information on the pivots, and solving the problem using the guesses. We believe this framework can lead to further results on k-clustering problems.

We propose a new convex programming relaxation for the weighted Nash social welfare (NSW) problem that achieves a matching (e^{1/e} ≈ 1.445)-approximation via the rounding algorithm of Feng and Li. Unlike the exponential-size configuration LP used in prior work, our formulation can be converted into a compact linear program of polynomial size, incurring only an additive loss of ln(1+ε) in the objective. This allows the program to be solved directly using standard LP solvers, without the ellipsoid method or dual separation oracles. In the unweighted case, we show that our convex program is equivalent to the restricted-spending Fisher market convex program of Cole and Gkatzelis, yielding a constructive proof that its integrality gap is exactly e^{1/e}. With a minor modification, our analysis also gives a simple proof of the e^{1/e} EF1 gap for the identical agent setting. Finally, we show that our convex programming technique extends to two unrelated machine scheduling problems, recovering the best-known approximation ratios with simpler analyses.

We show that under mild assumptions for a problem whose solutions admit a dynamic programming-like recurrence relation, we can still find a solution under additional packing constraints, which need to be satisfied approximately. The number of additional constraints can be very large, e.g., polynomial in the problem size. Technically, we reinterpret the dynamic programming subproblems and their solutions as a network design problem. Inspired by techniques from, e.g., the Directed Steiner Tree problem, we construct a strong LP relaxation, on which we then apply randomized rounding. Our approximation guarantees on the packing constraints have roughly the form of a (nє polylog n)-approximation in time nO(1/є), for any є > 0. By setting є=loglogn/logn, we obtain a polylogarithmic approximation in quasi-polynomial time, or by setting є as a constant, an nє-approximation in polynomial time.

We study the problem of allocating items to agents with submodular valuations with the goal of maximizing the weighted Nash social welfare (NSW). The best-known results for unweighted and weighted objectives are the (4+є) approximation given by Garg, Husic, Li, Végh, and Vondrák [STOC 2023] and the (233+є) approximation given by Feng, Hu, Li, and Zhang [STOC 2025], respectively.

We revisit the simultaneous approximation model for the correlation clustering problem introduced by Davies, Moseley, and Newman [Davies et al., 2024]. The objective is to find a clustering that minimizes given norms of the disagreement vector over all vertices. We present an efficient algorithm that produces a clustering that is simultaneously a 63.3-approximation for all monotone symmetric norms. This significantly improves upon the previous approximation ratio of 6348 due to Davies, Moseley, and Newman [Davies et al., 2024], which works only for 𝓁_p-norms. To achieve this result, we first reduce the problem to approximating all top-k norms simultaneously, using the connection between monotone symmetric norms and top-k norms established by Chakrabarty and Swamy [Chakrabarty and Swamy, 2019]. Then we develop a novel procedure that constructs a 12.66-approximate fractional clustering for all top-k norms. Our 63.3-approximation ratio is obtained by combining this with the 5-approximate rounding algorithm by Kalhan, Makarychev, and Zhou [Kalhan et al., 2019]. We then demonstrate that with a loss of ε in the approximation ratio, the algorithm can be adapted to run in nearly linear time and in the MPC (massively parallel computation) model with poly-logarithmic number of rounds. By allowing a further trade-off in the approximation ratio to (359+ε), the number of MPC rounds can be reduced to a constant.

We study the fair k-set selection problem where we aim to select k sets from a given set system such that the (weighted) occurrence times that each element appears in these k selected sets are balanced, i.e., the maximum (weighted) occurrence times are minimized. By observing that a set system can be formulated into a bipartite graph G:=(L cup R, E), our problem is equivalent to selecting k vertices from R such that the maximum (weighted) number selected neighbors of vertices in L is minimized. The problem arises in a wide range of applications in various fields, such as machine learning, artificial intelligence, and operations research. We first prove that the problem is NP-hard even if the maximum degree Delta of the input bipartite graph is 3, and the problem is in P when Delta=2. We then show that the problem is also in P when the input set system forms a laminar family. Based on intuitive linear programming, we show that two rounding algorithms achieve O(log n/(log log n))-approximation on general bipartite graphs, and an independent rounding algorithm achieves O(log(Delta))-approximation on bipartite graphs with a maximum degree Delta. We demonstrate that our analysis is almost tight by providing a hard instance for this linear programming.

We revisit the unrelated machine scheduling problem with the weighted completion time objective. It is known that independent rounding achieves a 1.5 approximation for the problem, and many prior algorithms improve upon this ratio by leveraging strong negative correlation schemes. On each machine i, these schemes introduce strong negative correlation between events that some pairs of jobs are assigned to i, while maintaining non-positive correlation for all pairs.

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. CCL+24 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, CCL+24 showed how to find a feasible solution for the cluster LP in time $O(n^{\text{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.485+ε)$-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 $\widetilde O(2^{\text{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.485+ε)$-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.

In the Directed Steiner Tree (DST) problem, we are given a directed graph \(G=(V,E)\) on \(n\) vertices with edge-costs \(c\in{\mathbb{R}}_{\geq 0}^{E}\) , a root vertex \(r\in V\) , and a set \(K\subseteq V\setminus\{r\}\) of \(k\) terminals. The goal is to find a minimum-cost subgraph of \(G\) that contains a path from \(r\) to every terminal \(t\in 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^{\epsilon})\) for any constant \(\epsilon \gt 0\) , and the best quasi-polynomial-time approximation ratio of \(O\left(\frac{\log^{2}k}{\log\log k}\right)\) . Toward understanding this gap, we study the integrality gap of the standard flow linear programming relaxation for the problem. We show that the linear program (LP) has an integrality gap of \(\Omega(n^{0.0418})\) . Previously, the integrality gap of the LP is only known to be \(\Omega\left(\frac{\log^{2}n}{\log\log n}\right)\) [Halperin et al., SODA’03 & SIAM J. Comput.] and \(\Omega(\sqrt{k})\) [Zosin-Khuller, SODA’02] in some instance with \(\sqrt{k}=O\left(\frac{\log n}{\log\log n}\right)\) . 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.

The paper revisits the Robust s-t Path problem, one of the most fundamental problems in robust optimization. In the problem, we are given a directed graph with n vertices and k distinct cost functions (scenarios) defined over edges, and aim to choose an s-t path such that the total cost of the path is always provable no matter which scenario is realized. Viewing each cost function as an agent, our goal is to find a fair s-t path, which minimizes the maximum cost among all agents. The problem is NP-hard to approximate within a factor of o(log k) unless NP ⊆ DTIME(npoly logn), and the best-known approximation ratio is Õ (√n), which is based on the natural flow linear program. A longstanding open question is whether we can achieve a polylogarithmic approximation for the problem; it remains open even if a quasi-polynomial running time is allowed. Our main result is a O (log n log k) approximation for the Robust s-t Path problem in quasipolynomial time, solving the open question in the quasi-polynomial time regime. The algorithm is built on a novel linear program formulation for a decision-tree-type structure, which enables us to overcome the Ω (√n) integrality gap for the natural flow LP. Furthermore, we show that for graphs with bounded treewidth, the quasi-polynomial running time can be improved to a polynomial. We hope our techniques can offer new insights into this problem and other related problems in robust optimization. © Shi Li, Chenyang Xu, and Ruilong Zhang.

We give the first $O(1)$-approximation for the weighted Nash Social Welfare problem with additive valuations. The approximation ratio we obtain is $e^{1/e} + ε\approx 1.445 + ε$, which matches the best known approximation ratio for the unweighted case. Both our algorithm and analysis are simple. We solve a natural configuration LP for the problem, and obtain the allocation of items to agents using a randomized version of the Shmoys-Tardos rounding algorithm developed for unrelated machine scheduling problems. In the analysis, we show that the approximation ratio of the algorithm is at most the worst gap between the Nash social welfare of the optimum allocation and that of an EF1 allocation, for an unweighted Nash Social Welfare instance with identical additive valuations. This was shown to be at most $e^{1/e} \approx 1.445$ by Barman, Krishnamurthy and Vaish, leading to our approximation ratio.

Online load balancing for heterogeneous machines aims to minimize the makespan (maximum machine workload) by scheduling arriving jobs with varying sizes on different machines. In the adversarial setting, where an adversary chooses not only the collection of job sizes but also their arrival order, the problem is well-understood and the optimal competitive ratio is known to be Θ(log m) where m is the number of machines. In the more realistic random arrival order model, the understanding is limited. Previously, the best lower bound on the competitive ratio was only Ω(log log m).

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.

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.

We study nearly-linear time approximation algorithms for non-preemptive scheduling problems in two settings: the unrelated machine setting, and the identical machine with job precedence constraints setting, under the well-studied objectives such as makespan and weighted completion time. For many problems, we develop nearly-linear time approximation algorithms with approximation ratios matching the current best ones achieved in polynomial time. Our main technique is linear programming relaxation. For the unrelated machine setting, we formulate mixed packing and covering LP relaxations of nearly-linear size, and solve them approximately using the nearly-linear time solver of Young. For the makespan objective, we develop a rounding algorithm with $(2+ε)$-approximation ratio. For the weighted completion time objective, we prove the LP is as strong as the rectangle LP used by Im and Li, leading to a nearly-linear time $(1.45 + ε)$-approximation for the problem. For problems in the identical machine with precedence constraints setting, the precedence constraints can not be formulated as packing or covering constraints. To achieve the nearly-linear running time, we define a polytope for the constraints, and leverage the multiplicative weight update (MWU) method with an oracle which always returns solutions in the polytope.

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 Lk-norms of machine loads, inspired by [Kalaitzis et al. SODA 2017], we give better approximation algorithms. In particular we give a -approximation for the L2-norm which improves upon the former -approximations due to [Azar-Epstein STOC 2005] and [Kumar et al. JACM 2009].

We consider the recourse version of the classical online load balancing problem on unrelated machines, where the algorithm is allowed to re-assign prior jobs. We give a (2+є)-competitive algorithm for the problem with Oє(logn) amortized recourse per job. This is the first O(1)-competitive algorithm for the problem with non-trivial recourse, and the competitive ratio nearly matches the long-standing best-known offline approximation guarantee. We also show an O(loglogn/logloglogn)-competitive algorithm for the problem with O(1) amortized recourse. The best-known bounds from prior work are O(loglogn)-competitive algorithms with O(1) amortized recourse due to Gupta et al., for the special case of the restricted assignment model.

We study the facility location problem under the constraints imposed by local differential privacy (LDP). Recently, Gupta et al. (2010) and Esencayi et al. (2019) proposed lower and upper bounds for the problem on the central differential privacy (DP) model where a trusted curator first collects all data and processes it. In this paper, we focus on the LDP model, where we protect a client’s participation in the facility location instance. Under the HST metric, we show that there is a non-interactive $\epsilon$-LDP algorithm achieving $O(n^{1/4}/\epsilon^2)$-approximation ratio, where $n$ is the size of the metric. On the negative side, we show a lower bound of $\Omega(n^{1/4}/\sqrt{\epsilon})$ on the approximation ratio for any non-interactive $\epsilon$-LDP algorithm. Thus, our results are tight up to a polynomial factor of $\epsilon$. Moreover, unlike previous results, our results generalize to non-uniform facility costs.

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 order. Specifically, we study a problem where k vehicles of capacity c are serving a set of requests ordering food from one restaurant. After a request arrives, it can be served by a vehicle moving from the restaurant to its delivery location. We are interested in serving all requests while minimizing the maximum flow-time, i.e., the maximum time length a customer waits to receive his/her food after submitting the order. We show that the problem is hard in both offline and online settings even when k = 1 and c = ∞: There is a hardness of approximation of Ω(n) for the offline problem, and a lower bound of Ω(n) on the competitive ratio of any online algorithm, where n is number of points in the metric. We circumvent the strong negative results in two directions. Our main result is an O(1)-competitive online algorithm for the uncapacitated (i.e, c = ∞) food delivery problem on tree metrics; we also have negative result showing that the condition c = ∞ is needed. Then we explore the speed-augmentation model where our online algorithm is allowed to use vehicles with faster speed. We show that a moderate speeding factor leads to a constant competitive ratio, and we prove a tight trade-off between the speeding factor and the competitive ratio.

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.

The active-time scheduling problem considers the problem of scheduling preemptible jobs with windows (release times and deadlines) on a parallel machine that can schedule up to g jobs during each timestep. The goal in the active-time problem is to minimize the number of active steps, i.e., timesteps in which at least one job is scheduled.

Directed Steiner Tree (DST) is a central problem in combinatorial optimization and theoretical computer science: Given a directed graph $$G=(V, E)$$ with edge costs $$c \in {\mathbb {R}}_{\ge 0}^E$$ , a root $$r \in V$$ and k terminals $$K\subseteq V$$ , we need to output the minimum-cost arborescence in G that contains an $$r \rightarrow t$$ path for every $$t \in K$$ . Recently, Grandoni, Laekhanukit and Li, and independently Ghuge and Nagarajan, gave quasi-polynomial time $$O(\log ^2k/\log \log k)$$ -approximation Algorithms for the problem, which are tight under popular complexity assumptions. In this paper, we consider the more general Degree-Bounded Directed Steiner Tree (DB-DST) problem, where we are additionally given a degree bound $$d_v$$ on each vertex $$v \in V$$ , and we require that every vertex v in the output tree has at most $$d_v$$ children. We give a quasi-polynomial time $$(O(\log n \log k), O(\log ^2 n))$$ -bicriteria approximation: The Algorithm produces a solution with cost at most $$O(\log n\log k)$$ times the cost of the optimum solution that violates the degree constraints by at most a factor of $$O(\log ^2n)$$ . This is the first non-trivial result for the problem. While our cost-guarantee is nearly optimal, the degree violation factor of $$O(\log ^2n)$$ is an $$O(\log n)$$ -factor away from the approximation lower bound of $$\Omega (\log n)$$ from the set-cover hardness. The hardness result holds even on the special case of the Degree-Bounded Group Steiner Tree problem on trees (DB-GST-T). With the hope of closing the gap, we study the question of whether the degree violation factor can be made tight for this special case. We answer the question in the affirmative by giving an $$(O(\log n\log k), O(\log n))$$ -bicriteria approximation Algorithm for DB-GST-T.

In this paper we introduce and study the online consistent k-clustering with outliers problem, generalizing the non-outlier version of the problem studied in Lattanzi-Vassilvitskii [18]. We show that a simple local-search based on-line algorithm can give a bicriteria constant approximation for the problem with O(k^2 log^2(nD)) swaps of medians (recourse) in total, where D is the diameter of the metric. When restricted to the problem without outliers, our algorithm is simpler, deterministic and gives better approximation ratio and recourse, compared to that of Lattanzi-Vassilvitskii [18].

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.

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).

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 algorithm needs to maintain good solutions at all time steps with only a few changes to the previously made decisions (called recourse). We show that the classic local search technique can lead to a (1+√2+ε)-competitive online algorithm for facility location with only O(log n/ε log 1/ε) amortized facility and client recourse, where n is the total number of clients arrived during the process. We then turn to the dynamic algorithm model for the problem, where the main goal is to design fast algorithms that maintain good solutions at all time steps. We show that the result for online facility location, combined with the randomized local search technique of Charikar and Guha [Charikar and Guha, 2005], leads to a (1+√2+ε)-approximation dynamic algorithm with total update time of Õ(n²) in the incremental setting against adaptive adversaries. The approximation factor of our algorithm matches the best offline analysis of the classic local search algorithm. Finally, we study the fully dynamic model for facility location, where clients can both arrive and depart. Our main result is an O(1)-approximation algorithm in this model with O(|F|) preprocessing time and O(nlog³ D) total update time for the HST metric spaces, where |F| is the number of potential facility locations. Using the seminal results of Bartal [Bartal, 1996] and Fakcharoenphol, Rao and Talwar [Fakcharoenphol et al., 2003], which show that any arbitrary N-point metric space can be embedded into a distribution over HSTs such that the expected distortion is at most O(log N), we obtain an O(log |F|) approximation with preprocessing time of O(|F|²log |F|) and O(nlog³ D) total update time. The approximation guarantee holds in expectation for every time step of the algorithm, and the result holds in the oblivious adversary model.

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.

We study approximation algorithms for problems of scheduling precedence constrained jobs with the objective of minimizing total weighted completion time, in identical and related machine models. We give algorithms that improve upon many previous 15- to 20-year-old state-of-the-art results. A major theme in these results is the use of time-indexed linear programming relaxations, which are quite natural for their respective problems. We also consider the scheduling problem of minimizing total weighted completion time on unrelated machines. The recent breakthrough result of [N. Bansal, A. Srinivasan, and O. Svensson, in Proceedings of the 48th Annual ACM Symposium on Theory of Computing, ACM, 2016, pp. 156--167] gave a (1.5-c)-approximation for the problem, based on a two-round lift-and-project of the SDP relaxation for the problem. Our main result is that a (1.5 - c)-approximation can also be achieved using a natural and considerably simpler time-indexed linear programming relaxation for the problem. We hope this relaxation can provide new insights into the problem.

In this paper we consider one of the most basic scheduling problems where jobs have their respective arrival times and deadlines. The goal is to schedule as many jobs as possible nonpreemptively by their respective deadlines on $m$ identical parallel machines. For the last decade, the best approximation ratio known for the single-machine case ($m = 1$) has been $1-1/e - \epsilon \approx 0.632$ due to Chuzhoy, Ostrovsky, and Rabani [FOCS 2001] and [MOR 2006]. We break this barrier and give an improved 0.644-approximation. For the multiple-machine case, we give an algorithm whose approximation guarantee becomes arbitrarily close to 1 as the number of machines increases. This improves upon the previous best $1 - 1/ (1 + 1/m)^m$ approximation due to Bar-Noy et al. [STOC 1999] and [SICOMP 2009], which converges to 1-1/e as $m$ goes to infinity. Our result for the multiple-machine case extends to the weighted throughput objective where jobs have different weights, and the goal is to schedule jobs with the maximum total weight. Our results show that the 1 - 1/e approximation factor widely observed in various coverage problems is not tight for the nonpreemptive maximum throughput scheduling problem.

Indoor localization has been an active research area given the popularity of Location-Based Services. The CSI fingerprinting based approach is one of the most practical and effective approaches since it can provide adequate accuracy with low overhead for users. The key drawback that limits its wide application is the huge amount of human effort required to build the fingerprint map. This paper is the first to explore addressing this limitation by automating CSI map construction using an Unmanned Aerial Vehicle (UAV). Given the limited battery capacity of commodity UAVs, it is extremely important yet challenging to optimize energy efficiency for the UAV during the CSI measurement task. To address this challenge, we formulate an energy optimization problem based on a novel graph model that includes the cost of possible actions for UAVs. We then transform the formulated problem to the classic Generalized Traveling Salesman Problem (GTSP), which can be solved efficiently. We implement the system on an off-the-shelf programmable drone equipped with a CSI measurement module. We achieve great energy efficiency improvement over the conventional coverage path planning algorithm. Meanwhile, accurate indoor localization can be achieved using the CSI data collected by our UAV system.

In this paper we study the facility location problem in the model of differential privacy (DP) with uniform facility cost. Specifically, we first show that under the hierarchically well-separated tree (HST) metrics and the super-set output setting that was introduced in Gupta et. al., there is an $\epsilon$-DP algorithm that achieves an $O(\frac{1}{\epsilon})$(expected multiplicative) approximation ratio; this implies an $O(\frac{\log n}{\epsilon})$ approximation ratio for the general metric case, where $n$ is the size of the input metric. These bounds improve the best-known results given by Gupta et. al. In particular, our approximation ratio for HST-metrics is independent of $n$, and the ratio for general metrics is independent of the aspect ratio of the input metric. On the negative side, we show that the approximation ratio of any $\epsilon$-DP algorithm is lower bounded by $\Omega(\frac{1}{\sqrt{\epsilon}})$, even for instances on HST metrics with uniform facility cost, under the super-set output setting. The lower bound shows that the dependence of the approximation ratio for HST metrics on $\epsilon$ can not be removed or greatly improved. Our novel methods and techniques for both the upper and lower bound may find additional applications.

In this paper, we prove topology dependent bounds on the number of rounds needed to compute Functional Aggregate Queries ($\FAQ$s) studied by Abo Khamis et al. [PODS 2016] in a synchronous distributed network under the model considered by Chattopadhyay et al. [FOCS 2014, SODA 2017]. Unlike the recent work on computing database queries in the Massively Parallel Computation model, in the model of Chattopadhyay et al., nodes can communicate only via private point-to-point channels and we are interested in bounds that work over an \em arbitrary communication topology. This model, which is closer to the well-studied $\congest$ model in distributed computing and generalizes Yao's two party communication complexity model, has so far only been studied for problems that are common in the two-party communication complexity literature. This is the first work to consider more practically motivated problems in this distributed model. For the sake of exposition, we focus on two specific problems in this paper: Boolean Conjunctive Query ($\BCQ$) and computing variable/factor marginals in Probabilistic Graphical Models (PGMs). We obtain tight bounds on the number of rounds needed to compute such queries as long as the underlying hypergraph of the query is $O(1)$-degenerate and has $O(1)$-arity. In particular, the $O(1)$-degeneracy condition covers most well-studied queries that are efficiently computable in the centralized computation model like queries with constant treewidth. These tight bounds depend on a new notion of 'width' (namely \em internal-node-width ) for Generalized Hypertree Decompositions (GHDs) of acyclic hypergraphs, which minimizes the number of internal nodes in a sub-class of GHDs. To the best of our knowledge, this width has not been studied explicitly in the theoretical database literature. Finally, we consider the problem of computing the product of a vector with a chain of matrices and prove tight bounds on its round complexity (over a finite field of two elements) using a novel min-entropy based argument.

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

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.

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.

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.)

We consider stochastic settings for clustering, and develop provably-good approximation algorithms for a number of these notions. These algorithms yield better approximation ratios compared to the usual deterministic clustering setting. Additionally, they offer a number of advantages including clustering which is fairer and has better long-term behavior for each user. In particular, they ensure that every user is guaranteed to get good service (on average). We also complement some of these with impossibility results.

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^{{poly}\log (k)}$. By assuming the projection game conjecture and ${NP}\not\subseteq{\bigcap}_{0<\epsilon<1}{ZPTIME}(2^{n^\epsilon})$ and adjusting the parameters in the hardness result of [Halperin and Krauthgamer, Polylogarithmic inapproximability, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 585--594], we show the matching lower bound of $\Omega(\log^2{k}/\log\log{k})$ for the class of quasi-polynomial time algorithms, meaning that our approximation ratio is asymptotically the best possible. Our algorithm is proceeded by reducing DST to an intermediate problem, namely, the group Steiner tree on trees with dependency constraint problem, which we approximate using the framework developed by [Rothvoß, Directed Steiner Tree and the Lasserre Hierarchy, preprint, arxiv:1111.5473, 2011] and [Friggstad et al., Linear programming hierarchies suffice for directed Steiner tree, in Proceedings of the 17th Annual Conference on Integer Programming and Combinatorial Optimization, 2014, pp. 285--296].

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, in large data clusters, and in data centers. Along with makespan, flow-time, which measures the length of time a job spends in a system before it completes, is arguably the most important metric to measure the performance of a scheduling algorithm. In recent years, there has been a remarkable progress in understanding flow-time based objective functions in diverse settings such as unrelated machines scheduling, broadcast scheduling, multi-dimensional scheduling, to name a few. Yet, our understanding of the flow-time objective is limited mostly to the scenarios where jobs have no dependencies. On the other hand, in almost all real world applications, think of MapReduce settings for example, jobs have dependencies that need to be respected while making scheduling decisions. In this paper, we take first steps towards understanding this complex problem. In particular, we consider two classical scheduling problems that capture dependencies across jobs: 1) concurrent open-shop scheduling (COSSP) and 2) precedence constrained scheduling. Our main motivation to study these problems specifically comes from their relevance to two scheduling problems that have gained importance in the context of data centers: co-flow scheduling and DAG scheduling. We design almost optimal approximation algorithms for COSSP and PCSP, and show hardness results.

We consider stochastic settings for clustering, and develop provably-good (approximation) algorithms for a number of these notions. These algorithms allow one to obtain better approximation ratios compared to the usual deterministic clustering setting. Additionally, they offer a number of advantages including providing fairer clustering and clustering which has better long-term behavior for each user. In particular, they ensure that every user is guaranteed to get good service (on average). We also complement some of these with impossibility results.

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.[10] 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+\epsilon)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.

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.

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.

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.

We study the non-uniform capacitated multi-item lot-sizing (CMILS) problem. In this problem, there is a set of demands over a planning horizon of T time periods and all demands must be satisfied on time. We can place an order at the beginning of each period s, incurring an ordering cost Ks. The total quantity of all products ordered at time s can not exceed a given capacity Cs. On the other hand, carrying inventory from time to time incurs inventory holding cost. The goal of the problem is to find a feasible solution that minimizes the sum of ordering and holding costs. Levi et al. (Levi, Lodi and Sviridenko, Mathmatics of Operations Research 33(2), 2008) gave a 2-approximation for the problem when the capacities Cs are the same. In this paper, we extend their result to the case of non-uniform capacities. That is, we give a constant approximation algorithm for the capacitated multi-item lot-sizing problem with general capacities. The constant approximation is achieved by adding an exponentially large set of new covering inequalities to the natural facility-location type linear programming relaxation for the problem. Along the way of our algorithm, we reduce the CMILS problem to two generalizations of the classic knapsack covering problem. We give LP-based constant approximation algorithms for both generalizations, via the iterative rounding technique.

In this article, we study the uniform capacitated k -median (CKM) problem. In the problem, we are given a set F of potential facility locations, a set C of clients, a metric d over F ∪ C , an upper bound k on the number of facilities that we can open, and an upper bound u on the number of clients that each facility can serve. We need to open a subset S ⊆ F of k facilities and connect clients in C to facilities in S 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 of 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 + ϵ. In other words, 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. It is our hope that this LP is the first step toward a constant approximation for CKM. The version that 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 facility 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.

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|rij| ΣjwjCjusing 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|rij, pmtn|ΣjwjCj. 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.

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 bound k on the number of open facilities. Using the natural LP relaxation for the problem, one can only hope to get the violation factor down to 2. Li [SODA'16] introduced a novel LP to go beyond the limit of 2 and gave a constant-factor approximation algorithm that opens (1 + epsilon)*k facilities. We use the configuration LP of Li [SODA'16] to give a constant-factor approximation for the Capacitated k-Median problem in a seemingly harder configuration: we violate only the capacities by 1 + epsilon. This result settles the problem as far as pseudo-approximation algorithms are concerned.

In the capacitated k-median (CKM) problem, we are given a set F of facilities, each facility i ∊ F with a capacity ui, 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 ui 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.

We study the classical Node-Disjoint Paths (NDP) problem: given an n-vertex graph G and a collection =(s1,t1),…,(sk,tk) 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 Ω(log1/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 Õ(n9/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.

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 pairs of vertices called 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 multi-commodity flow 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 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 ~ Ω ((log n ) 1/( c +1) ) for any constant congestion c . Prior to our work, the best approximation factor for EDPwC with congestion 2 was Õ( n 3/7 ), and the best algorithm achieving a polylogarithmic approximation required congestion 14.

We present a novel approximation algorithm for $k$-median that achieves an approximation guarantee of $1+\sqrt{3}+\epsilon$, improving upon the decade-old ratio of $3+\epsilon$. Our improved approximation ratio is achieved by exploiting the power of pseudo-approximation. More specifically, 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 $\alpha$-approximation algorithm for $k$-median, it is sufficient to give a pseudo-approximation algorithm that finds an $\alpha$-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 significantly smaller cost than that of opening only $k$ facilities. Second, we give such a pseudo-approximation algorithm with $\alpha=1+\sqrt{3}+\epsilon$. Prior to our work, it was not even known whether opening $k+o(k)$ facilities would help improve the approximation ratio.

In this article, we consider the fault-tolerant k -median problem and give the first constant factor approximation algorithm for it. In the fault-tolerant generalization of the 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 alogarithmic 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 an HST by showing that the corresponding LP always has an integral optimal solution. We also consider the fault-tolerant facility location problem, in which 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 that work only for nonincreasing weight vectors.

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 (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.

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 2log1–ε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.

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 — ε.

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 Õ(log1,5 n) approximation algorithm for the problem improving upon the previous Õ(log 2 n) approximation. We also show an Ω(log1/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.

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 rj ≥ 1 distinct open facilities. The service cost of j is the sum of its distances to the rj 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 rjs 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 rj facilities. We give a simple constant factor approximation algorithm, generalizing several previous results which only work for nonincreasing weight vectors.

Vegetation phenology is closely connected to the terrestrial carbon budget, and interacts with the atmosphere through surface water and energy exchange. A comprehensive and detailed characterization of the spatio-temporal pattern of vegetation phenology can be used to improve the understanding of interactions between vegetation and climate in Africa. This research provides an approach to derive phenology time and trajectory parameters by optimally fitting a double-logistic curve to daily remotely sensed leaf area index (LAI) from the spinning enhanced visible and infrared imager. The proposed algorithm can reconstruct the temporal LAI trajectory based on the optimized parameters with a high accuracy, and provides user-defined phenological timing information (e.g., start/end of the growing season) and trajectory information (e.g., leaf emergence/senescence rate and length) using these fitted parameters. Both single and double growing-season cases have been considered with a spatial classification scheme implemented over Africa. The newly derived vegetation phenology of Africa exhibits emerging spatial patterns in growing season length, asymmetric green-up and green-off length/rate, and distinctive phenological features of cropland and natural vegetation. This approach has the potential to be applied globally, and the derived vegetation phenological information will improve dynamic vegetation modeling and climate prediction.

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.

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(√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̅(n3/7), and the best algorithm achieving a polylogarithmic approximation required congestion 14.

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(npoly log n). We then turn to study the more general group version of the problem (group=ICF), in which we are given a collection (S1,T1),...,(Sk,Tk)} of pairs of vertex subsets, and for each 1 ≤ i ≤ k, a demand Di is specified. The goal is to find a maximum value λ and a collection P of paths, such that for each i, at least ⌊ λ ⋅ Di⌋ paths connect the vertices of Si to the vertices of Ti, while respecting the edge capacities. We show that for any 1 ≤ c ≤ O(log log n), no efficient algorithm can achieve a factor O(n1/(22c+3))-approximation with congestion c for the problem, unless NP ⊆ DTIME(nO(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 (Si,Ti).

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, EH) 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 Ω(log1/4k) 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.

We study the multicast capacity of large-scale random extended multihop wireless networks, where a number of wireless nodes are randomly located in a square region with side lengtha= √n, by use of Poisson distribution with density 1. All nodes transmit at a constant powerP, and the power decays with attenuation exponentα > 2. The data rate of a transmission is determined by theSINRasBlog(1+ SINR), whereBis the bandwidth. There arensrandomly and independently chosen multicast sessions. Each multicast session haskrandomly chosen terminals. We show that whenk≤ θ1[(n)/((logn)2α+ 6)] andns≥ θ2n1/2+β, the capacity that each multicast session can achieve, with high probability, is at leastc8[(√n)/(ns√k)], whereθ1,θ2, andc8are some special constants andβ > 0is any positive real number. We also show that fork=O( [(n)/(log2n)]) , the per-flow multicast capacity under Gaussian channel is at mostO([(√n)/(ns√k)]) when we have at leastns= Ω(logn) random multicast flows. Our result generalizes the unicast capacity for random networks using percolation theory.