We present the first polynomial-time algorithm for computing a near-optimal flow-expander decomposition. Given a graph G and a parameter ϕ, our algorithm removes at most a ϕlog^{1+o(1)}n fraction of edges so that every remaining connected component is a ϕ-flow-expander (a stronger guarantee than being a ϕ-cut-expander). This achieves overhead log^{1+o(1)}n, nearly matching the Ω(log n) graph-theoretic lower bound that already holds for cut-expander decompositions, up to a log^{o(1)}n factor. Prior polynomial-time algorithms required removing O(ϕlog^{1.5}n) and O(ϕlog²n) fractions of edges to guarantee ϕ-cut-expander and ϕ-flow-expander components, respectively.

The Beck-Fiala Conjecture [Beck and Fiala, Discrete Appl. Math., 1981] asserts that any set system of n elements with degree k has combinatorial discrepancy O(√k). A substantial generalization is the Komlós Conjecture, which states that any m × n matrix with columns of unit ℓ2 length has discrepancy O(1).

The Correlated Pandora’s Problem posed by Chawla et al. (2020) generalizes the classical Pandora’s Problem by allowing the numbers inside the Pandora’s boxes to be correlated. It also generalizes the Min Sum Set Cover problem, and is related to the Uniform Decision Tree problem. This paper gives an optimal 4-approximation for the Correlated Pandora’s Problem, matching the lower bound of 4 from Min Sum Set Cover.

In 1981, Beck and Fiala [1] conjectured that given a set system $A \in\{0,1\}^{m \times n}$ with degree at most k (i.e., each column of A has at most k non-zeros), its combinatorial discrepancy $\operatorname{disc}(A):=\min _{x \in\{ \pm 1\}^{n}}\|A x\|_{\infty}$ is at most $O(\sqrt{k})$. Previously, the best-known bounds for this conjecture were either $O(k)$, first established by Beck and Fiala [1], or $O(\sqrt{k \log n})$, first proved by Banaszczyk [2].We give an algorithmic proof of an improved bound of $O(\sqrt{k \log \log n})$ whenever $k \geq \log ^{5} n$, thus matching the Beck-Fiala conjecture up to $O(\sqrt{\log \log n})$ for almost the full regime of k.

We examine the problem of numerically estimating the integral of a function f. The classical approaches to this problem are Monte Carlo (MC) and quasi-Monte Carlo (QMC) methods. MC methods use random samples to evaluate f and have error , where σ(f ) is the standard deviation of f. QMC methods are based on evaluating f at explicit point sets with low discrepancy, and as given by the classical Koksma- Hlawka inequality, they have error Õ (σHK(f )/n ), where σΗΚ(f ) is the variation of f in the sense of Hardy and Krause. These two methods have distinctive advantages and shortcomings, and a fundamental question is to find a method that combines the advantages of both.

No abstract available.

Coresets are arguably the most popular compression paradigm for center-based clustering objectives such as$k$-means. Given a point set$P$, a coreset$\Omega$is a small, weighted summary that preserves the cost of all candidate solutions$S$up to a$(1\pm\varepsilon)$factor. For$k$-means in$d$-dimensional Euclidean space the cost for solution$S$is$\Sigma_{p\in P}{\min}_{s\in S}\Vert p-s\Vert ^2$. A very popular method for coreset construction, both in theory and practice, is Sensitivity Sampling, where points are sampled in proportion to their importance. We show that Sensitivity Sampling yields optimal coresets of size$\widetilde{O}(k/\varepsilon^{2}\min(\sqrt{k},\varepsilon^{-2}))$for worst-case instances. Uniquely among all known coreset algorithms, for well-clusterable data sets with$\Omega(1)$, cost stability, Sensitivity Sampling gives coresets of size$\widetilde{O}(k/\varepsilon^{2})$, improving over the worst-case lower bound. Notably, Sensitivity Sampling does not have to know the cost stability in order to exploit it: it is appropriately sensitive to the clusterability of the data set while being oblivious to it. We also show that any coreset for stable instances consisting of only input points must have size$\Omega(k/\varepsilon^{2})$. Our results for Sensitivity Sampling also extend to the k-median problem, and more general metric spaces.

We study graph ordering problems with a min-max objective. A classical problem of this type is cutwidth, where given a graph we want to order its vertices such that the number of edges crossing any point is minimized. We give a$\log^{1+o(1)}(n)$approximation for the problem, substantially improving upon the previous poly-logarithmic guarantees based on the standard recursive balanced partitioning approach of Leighton and Rao (FOCS'88). Our key idea is a new metric decomposition procedure that is suitable for handling min-max objectives, which could be of independent interest. We also use this to show other results, including an improved$\log^{1+o(1)}(n)$approximation for computing the pathwidth of a graph.

Training large AI models on numerous GPUs consumes a massive amount of energy, making power delivery one of the largest limiting factors in building and operating datacenters for AI workloads. However, we observe that not all energy consumed during training directly contributes to end-to-end throughput; a significant portion can be removed without slowing down training. We call this portion energy bloat.

We give a simple proof of the matrix Spencer conjecture up to poly-logarithmic rank: given symmetric d × d matrices A1,…,An each with ||Ai||op ≤ 1 and rank at most n/log3 n, one can efficiently find ± 1 signs x1,…,xn such that their signed sum has spectral norm ||∑i=1n xi Ai||op = O(√n). This result also implies a logn − Ω( loglogn) qubit lower bound for quantum random access codes encoding n classical bits with advantage ≫ 1/√n.

Abstract. We study the Generalized Min Sum Set Cover (GMSSC) problem, wherein given a collection of hyperedges [Formula: see text] with arbitrary covering requirements [Formula: see text], the goal is to find an ordering of the vertices to minimize the total cover time of the hyperedges; a hyperedge [Formula: see text] is considered covered by the first time when [Formula: see text] and many of its vertices appear in the ordering. We give a [Formula: see text] approximation algorithm for GMSSC, coming close to the best possible bound of 4, already for the classical special case (with all [Formula: see text]) of Min Sum Set Cover (MSSC) studied by Feige, Lovász, and Tetali, and improving upon the previous best known bound of [Formula: see text] due to Im, Sviridenko, and van der Zwaan. Our algorithm is based on transforming the LP solution by a suitable kernel and applying randomized rounding. As part of the analysis of our algorithm, we also derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which might be of independent interest and broader utility. Min Sum Vertex Cover (MSVC) is a well-known special case of MSSC in which the input hypergraph is a graph (i.e., [Formula: see text]) and [Formula: see text] for every edge [Formula: see text]. We give a [Formula: see text] approximation for MSVC and show a matching integrality gap for the natural LP relaxation. This improves upon the previous best [Formula: see text] approximation of Barenholz, Feige, and Peleg. Finally, we revisit MSSC and consider the [Formula: see text] norm of cover-time of the hyperedges. Using a dual fitting argument, we show that the natural greedy algorithm achieves tight, up to NP-hardness, approximation guarantees of [Formula: see text] for all [Formula: see text], giving another proof of the result of Golovin, Gupta, Kumar, and Tangwongsan, and showing its tightness up to NP-hardness. For [Formula: see text], this gives yet another proof of the 4 approximation for MSSC.

The generalized k -server problem is a far-reaching extension of the k -server problem with several applications. Here, each server s i lies in its own metric space M i . A request is a k -tuple r = ( r 1 , r 2 ,… , r k , which is served by moving some server s i to the point r i ∈ M i , and the goal is to minimize the total distance traveled by the servers. Despite much work, no f ( k )-competitive algorithm is known for the problem for k > 2 servers, even for special cases such as uniform metrics and lines. Here, we consider the problem in uniform metrics and give the first f ( k )-competitive algorithms for general k . In particular, we obtain deterministic and randomized algorithms with competitive ratio k · 2 k and O ( k 3 log k ), respectively. Our deterministic bound is based on a novel application of the polynomial method to online algorithms, and essentially matches the long-known lower bound of 2 k -1. We also give a 2 2 O(k) -competitive deterministic algorithm for weighted uniform metrics, which also essentially matches the recent doubly exponential lower bound for the problem.

We study a unified approach and algorithm for constructive discrepancy minimization based on a stochastic process. By varying the parameters of the process, one can recover various state-of-the-art results. We demonstrate the flexibility of the method by deriving a discrepancy bound for smoothed instances, which interpolates between known bounds for worst-case and random instances.

The Aaronson-Ambainis conjecture (Theory of Computing’14) says that every low-degree bounded polynomial on the Boolean hypercube has an influential variable. This conjecture, if true, would imply that the acceptance probability of every d-query quantum algorithm can be well-approximated almost everywhere (i.e., on almost all inputs) by a poly(d)-query classical algorithm. We prove a special case of the conjecture: in every completely bounded degree-d block-multilinear form with constant variance, there always exists a variable with influence at least 1/poly(d). In a certain sense, such polynomials characterize the acceptance probability of quantum query algorithms, as shown by Arunachalam, Briët and Palazuelos (SICOMP’19). As a corollary we obtain efficient classical almost-everywhere simulation for a particular class of quantum algorithms that includes for instance k-fold Forrelation. Our main technical result relies on connections to free probability theory.

We introduce a general online allocation problem that connects several of the most fundamental problems in online optimization. Let M be an n-point metric space. Consider a resource that can be allocated in arbitrary fractions to the points of M. At each time t, a convex monotone cost function c_t: [0,1] → ℝ_+ appears at some point r_t ∈ M. In response, an algorithm may change the allocation of the resource, paying movement cost as determined by the metric and service cost c_t(x_{r_t}), where x_{r_t} is the fraction of the resource at r_t at the end of time t. For example, when the cost functions are c_t(x) = α x, this is equivalent to randomized MTS, and when the cost functions are c_t(x) = ∞⋅1_{x < 1/k}, this is equivalent to fractional k-server. Because of an inherent scale-freeness property of the problem, existing techniques for MTS and k-server fail to achieve similar guarantees for metric allocation. To handle this, we consider a generalization of the online multiplicative update method where we decouple the rate at which a variable is updated from its value, resulting in interesting new dynamics. We use this to give an O(log n)-competitive algorithm for weighted star metrics. We then show how this corresponds to an extension of the online mirror descent framework to a setting where the regularizer is time-varying. Using this perspective, we further refine the guarantees of our algorithm. We also consider the case of non-convex cost functions. Using a simple 𝓁₂²-regularizer, we give tight bounds of Θ(n) on tree metrics, which imply deterministic and randomized competitive ratios of O(n²) and O(nlog n) respectively on arbitrary metrics.

In the 2-choice allocation problem, m balls are placed into n bins, and each ball must choose between two random bins $i,j\in[n]$ that it has been assigned to. It has been known for more than two decades, that if each ball follows the GREEDY strategy (i.e., always pick the less-full bin), then the maximum load will be $m/n+O(\log\log n)$ with high probability in n (and $m/n+O(\log m)$ with high probability in m). It has remained an open question whether the same bounds hold in the dynamic version of the same game, where balls are inserted/deleted with no more than m balls present at a time.We show that, somewhat surprisingly, these bounds do not hold in the dynamic setting: already on 4 bins, there exists a sequence of insertions/deletions that cause the GREEDY strategy to incur a maximum load of $m/4+\Omega(\sqrt{m})$ with probability $\Omega(1)$—this is the same bound that one gets in the single-choice allocation model where each ball is assigned to a random bin!This raises the question of whether any 2-choice allocation strategy can offer a strong bound in the dynamic setting. Our second result answers this question in the affirmative: we present a new strategy, called MODULATEDGREEDY, that guarantees a maximum load of $m/n+O(\log m)$, at any given moment, with high probability in m. We also show how to generalize ModulatedGreedy to obtain dynamic guarantees for the $(1+\beta)$-choice setting, and for the setting of balls-and-bins on a graph.Finally, we consider an extension of the dynamic setting in which balls can be reinserted after they are deleted, and where the pair i, j that a given ball uses is consistent across insertions. This seemingly small modification renders tight load balancing impossible: on 4 bins, any balls-and-bins strategy that is oblivious to the specific identities of balls being inserted/deleted must allow for a maximum load of $m/4+\mathrm{poly}(m)$ at some point in the first poly (m) insertions/deletions, with high probability in m. This is a remarkable departure from the m=n case where the maximum load of O(loglogn) holds independently of whether reinsertions are allowed or not.

The well-known Komlós conjecture states that given n vectors in ℝ^d with Euclidean norm at most one, there always exists a ± 1 coloring such that the 𝓁_∞ norm of the signed-sum vector is a constant independent of n and d. We prove this conjecture in a smoothed analysis setting where the vectors are perturbed by adding a small Gaussian noise and when the number of vectors n = ω(d log d). The dependence of n on d is the best possible even in a completely random setting. Our proof relies on a weighted second moment method, where instead of considering uniformly randomly colorings we apply the second moment method on an implicit distribution on colorings obtained by applying the Gram-Schmidt walk algorithm to a suitable set of vectors. The main technical idea is to use various properties of these colorings, including subgaussianity, to control the second moment.

A well-known result of Banaszczyk in discrepancy theory concerns the prefix discrepancy problem (also known as the signed series problem): given a sequence of $T$ unit vectors in $\mathbb{R}^d$, find $\pm$ signs for each of them such that the signed sum vector along any prefix has a small $\ell_\infty$-norm? This problem is central to proving upper bounds for the Steinitz problem, and the popular Komlós problem is a special case where one is only concerned with the final signed sum vector instead of all prefixes. Banaszczyk gave an $O(\sqrt{\log d+ \log T})$ bound for the prefix discrepancy problem. We investigate the tightness of Banaszczyk's bound and consider natural generalizations of prefix discrepancy: We first consider a smoothed analysis setting, where a small amount of additive noise perturbs the input vectors. We show an exponential improvement in $T$ compared to Banaszczyk's bound. Using a primal-dual approach and a careful chaining argument, we show that one can achieve a bound of $O(\sqrt{\log d+ \log\!\log T})$ with high probability in the smoothed setting. Moreover, this smoothed analysis bound is the best possible without further improvement on Banaszczyk's bound in the worst case. We also introduce a generalization of the prefix discrepancy problem where the discrepancy constraints correspond to paths on a DAG on $T$ vertices. We show that an analog of Banaszczyk's $O(\sqrt{\log d+ \log T})$ bound continues to hold in this setting for adversarially given unit vectors and that the $\sqrt{\log T}$ factor is unavoidable for DAGs. We also show that the dependence on $T$ cannot be improved significantly in the smoothed case for DAGs. We conclude by exploring a more general notion of vector balancing, which we call combinatorial vector balancing. We obtain near-optimal bounds in this setting, up to poly-logarithmic factors.

We consider a natural semi-online model for weighted paging, where at any time the algorithm is given predictions, possibly with errors, about the next arrival of each page. The model is inspired by Belady's classic optimal offline algorithm for unweighted paging, and extends the recently studied model for learning-augmented paging [45, 50, 52] to the weighted setting. For the case of perfect predictions, we provide an ℓ-competitive deterministic and an O(log ℓ)-competitive randomized algorithm, where ℓ is the number of distinct weight classes. Both these bounds are tight, and imply an O(log W)- and O(log log W)-competitive ratio, respectively, when the page weights lie between 1 and W. Previously, it was not known how to use these predictions in the weighted setting and only bounds of k and O(log k) were known, where k is the cache size. Our results also generalize to the interleaved paging setting and to the case of imperfect predictions, with the competitive ratios degrading smoothly from O(ℓ) and O(log ℓ) to O(k) and O(log k), respectively, as the prediction error increases. Our results are based on several insights on structural properties of Belady's algorithm and the sequence of page arrival predictions, and novel potential functions that incorporate these predictions. For the case of unweighted paging, the results imply a very simple potential function based proof of the optimality of Belady's algorithm, which may be of independent interest.

The graphical balls-into-bins process is a generalization of the classical 2-choice balls-into-bins process, where the bins correspond to vertices of an arbitrary underlying graph G. At each time step an edge of G is chosen uniformly at random, and a ball must be assigned to either of the two endpoints of this edge. The standard 2-choice process corresponds to the case of G=Kn.

We relate discrepancy theory with the classic scheduling problems of minimizing max flow time and total flow time on unrelated machines. Specifically, we give a general reduction that allows us to transfer discrepancy bounds in the prefix Beck-Fiala (bounded ℓ1-norm) setting to bounds on the flow time of an optimal schedule. Combining our reduction with a deep result proved by Banaszczyk via convex geometry, give guarantees of O(√logn) and O(√logn logP) for max flow time and total flow time, respectively, improving upon the previous best guarantees of O(logn) and O(logn logP). Apart from the improved guarantees, the reduction motivates seemingly easy versions of prefix discrepancy questions: any constant bound on prefix Beck-Fiala where vectors have sparsity two (sparsity one being trivial) would already yield tight guarantees for both max flow time and total flow time. While known techniques solve this case when the entries take values in {−1,0,1}, we show that they are unlikely to transfer to the more general 2-sparse case of bounded ℓ1-norm.

Semidefinite programming is a powerful tool in the design and analysis of approximation algorithms for combinatorial optimization problems. In particular, the random hyperplane rounding method of Goemans and Williamson [ 31 ] has been extensively studied for more than two decades, resulting in various extensions to the original technique and beautiful algorithms for a wide range of applications. Despite the fact that this approach yields tight approximation guarantees for some problems, e.g., Max-Cut , for many others, e.g., Max-SAT and Max-DiCut , the tight approximation ratio is still unknown. One of the main reasons for this is the fact that very few techniques for rounding semi-definite relaxations are known. In this work, we present a new general and simple method for rounding semi-definite programs, based on Brownian motion. Our approach is inspired by recent results in algorithmic discrepancy theory. We develop and present tools for analyzing our new rounding algorithms, utilizing mathematical machinery from the theory of Brownian motion, complex analysis, and partial differential equations. Focusing on constraint satisfaction problems, we apply our method to several classical problems, including Max-Cut , Max-2SAT , and Max-DiCut , and derive new algorithms that are competitive with the best known results. To illustrate the versatility and general applicability of our approach, we give new approximation algorithms for the Max-Cut problem with side constraints that crucially utilizes measure concentration results for the Sticky Brownian Motion, a feature missing from hyperplane rounding and its generalizations.

We consider the following general scheduling problem studied recently by Moseley [27]. There are n jobs, all released at time 0, where job j has size pj and an associated arbitrary non-decreasing cost function fj of its completion time. The goal is to find a schedule on m machines with minimum total cost. We give an O(1) approximation for the problem, improving upon the previous O(log log nP) bound (P is the maximum to minimum size ratio), and resolving the open question in [27]. We first note that the scheduling problem can be reduced to a clean geometric set cover problem where points on a line with arbitrary demands, must be covered by a minimum cost collection of given intervals with non-uniform capacity profiles. Unfortunately, current techniques for such problems based on knapsack cover inequalities and low union complexity, completely lose the geometric structure in the non-uniform capacity profiles and incur at least an Ω(log log P) loss. To this end, we consider general covering problems with non-uniform capacities, and give a new method to handle capacities in a way that completely preserves their geometric structure. This allows us to use sophisticated geometric ideas in a black-box way to avoid the Ω(log log P) loss in previous approaches. In addition to the scheduling problem above, we use this approach to obtain O(1) or inverse Ackermann type bounds for several basic capacitated covering problems.

We study the generalized min sum set cover (GMSSC) problem, wherein given a collection of hyperedges E with arbitrary covering requirements {ke ∊ Z+ : e ∊ E}, the goal is to find an ordering of the vertices to minimize the total cover time of the hyperedges; a hyperedge e is considered covered by the first time when ke many of its vertices appear in the ordering. We give a 4.642 approximation algorithm for GMSSC, coming close to the best possible bound of 4, already for the classical special case (with all ke = 1) of min sum set cover (MSSC) studied by Feige, Lovász and Tetali [11], and improving upon the previous best known bound of 12.4 due to Im, Sviridenko and van der Zwaan [20]. Our algorithm is based on transforming the LP solution by a suitable kernel and applying randomized rounding. This also gives an LP-based 4 approximation for MSSC. As part of the analysis of our algorithm, we also derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which might be of independent interest and broader utility. Another well-known special case is the min sum vertex cover (MSVC) problem, in which the input hypergraph is a graph (i.e., |e| = 2) and ke = 1, for every edge e ∊ E. We give a 16/9 ≃ 1.778 approximation for MSVC, and show a matching integrality gap for the natural LP relaxation. This improves upon the previous best 1.999946 approximation of Barenholz, Feige and Peleg [6]. (The claimed 1.79 approximation result of Iwata, Tetali and Tripathi [21] for the MSVC turned out have an unfortunate, seemingly unfixable, mistake in it.) Finally, we revisit MSSC and consider the ℓp norm of cover-time of the hyperedges. Using a dual fitting argument, we show that the natural greedy algorithm simultaneously achieves approximation guarantees of (p + 1)1+1/p, for all p ≥ 1, giving another proof of the result of Golovin, Gupta, Kumar and Tangwongsan [13], and showing its tightness up to NP-hardness. For p = 1, this gives yet another proof of the 4 approximation for MSSC.

In the stochastic online vector balancing problem, vectors v1, v2, …, vT chosen independently from an arbitrary distribution in ℝn arrive one-by-one and must be immediately given a ± sign. The goal is to keep the norm of the discrepancy vector, i.e., the signed prefix-sum, as small as possible for a given target norm. We consider some of the most well-known problems in discrepancy theory in the above online stochastic setting, and give algorithms that match the known offline bounds up to polylog(nT) factors. This substantially generalizes and improves upon the previous results of Bansal, Jiang, Singla, and Sinha (STOC' 20). In particular, for the Komlós problem where ‖vt‖2 ≤ 1 for each t, our algorithm achieves Õ(1) discrepancy with high probability, improving upon the previous Õ(n3/2) bound. For Tusnády's problem of minimizing the discrepancy of axis-aligned boxes, we obtain an O(logd+4T) bound for arbitrary distribution over points. Previous techniques only worked for product distributions and gave a weaker O(log2d+1 T) bound. We also consider the Banaszczyk setting, where given a symmetric convex body K with Gaussian measure at least 1/2, our algorithm achieves Õ(1) discrepancy with respect to the norm given by K for input distributions with sub-exponential tails. Our results are based on a new potential function approach. Previous techniques consider a potential that penalizes large discrepancy, and greedily chooses the next color to minimize the increase in potential. Our key idea is to introduce a potential that also enforces constraints on how the discrepancy vector evolves, allowing us to maintain certain anti-concentration properties. We believe that our techniques to control the evolution of states could find other applications in stochastic processes and online algorithms. For the Banaszczyk setting, we further enhance this potential by combining it with ideas from generic chaining. Finally, we also extend these results to the setting of online multicolor discrepancy.

We study the writeback-aware caching problem, a variant of classic paging where paging requests that modify data and requests that leave data intact are treated differently. We give an O(łog^2 k) competitive randomized algorithm, answering an open question of Beckmann ηl~BGHM20 and Even et al. (21) about the existence of a randomized poly-logarithmic competitive algorithm. Our algorithm also works for arbitrary page weights. We also give an O(k) competitive deterministic algorithm, extending the previous result of Beckmann et al. BGHM20 to the weighted setting.

Aaronson and Ambainis (SICOMP ‘18) showed that any partial function on N bits that can be computed with an advantage δ over a random guess by making q quantum queries, can also be computed classically with an advantage δ/2 by a randomized decision tree making Oq(N1−1/2qδ−2) queries. Moreover, they conjectured the k-Forrelation problem — a partial function that can be computed with q = ⌈ k/2 ⌉ quantum queries — to be a suitable candidate for exhibiting such an extremal separation.

We consider the problem of scheduling jobs on unrelated machines so as to minimize the sum of weighted completion times. Our main result is a $(\nicefrac{3}{2}-c)$-approximation algorithm for some fixed $c>0$, improving upon the long-standing bound of $\nicefrac{3}{2}$. To do this, we first introduce a new lift-and-project-based SDP relaxation for the problem. This is necessary, as the previous convex programming relaxations have an integrality gap of $\nicefrac{3}{2}$. Second, we give a new general bipartite-rounding procedure that produces an assignment with certain strong negative correlation properties.

Semi-definite programming is a powerful tool in the design and analysis of approximation algorithms for combinatorial optimization problems. In particular, the random hyperplane rounding method of Goemans and Williamson [23] has been extensively studied for more than two decades, resulting in various extensions to the original technique and beautiful algorithms for a wide range of applications. Despite the fact that this approach yields tight approximation guarantees for some problems, e.g., Max-Cut, for many others, e.g., Max-SAT and Max-DiCut, the tight approximation ratio is still unknown. One of the main reasons for this is the fact that very few techniques for rounding semi-definite relaxations are known. In this work, we present a new general and simple method for rounding semi-definite programs, based on Brownian motion. Our approach is inspired by recent results in algorithmic discrepancy theory. We develop and present tools for analyzing our new rounding algorithms, utilizing mathematical machinery from the theory of Brownian motion, complex analysis, and partial differential equations. Focusing on constraint satisfaction problems, we apply our method to several classical problems, including Max-Cut, Max-2SAT, and Max-DiCut, and derive new algorithms that are competitive with the best known results. To illustrate the versatility and general applicability of our approach, we give new approximation algorithms for the Max-Cut problem with side constraints that crucially utilizes measure concentration results for the Sticky Brownian Motion, a feature missing from hyperplane rounding and its generalizations.

We consider an online vector balancing question where T vectors, chosen from an arbitrary distribution over [−1,1] n , arrive one-by-one and must be immediately given a ± sign. The goal is to keep the discrepancy—the ℓ∞-norm of any signed prefix-sum—as small as possible. A concrete example of this question is the online interval discrepancy problem where T points are sampled one-by-one uniformly in the unit interval [0,1], and the goal is to immediately color them ± such that every sub-interval remains always nearly balanced. As random coloring incurs Ω(T 1/2) discrepancy, while the worst-case offline bounds are Θ(√n log(T/n)) for vector balancing and 1 for interval balancing, a natural question is whether one can (nearly) match the offline bounds in the online setting for these problems. One must utilize the stochasticity as in the worst-case scenario it is known that discrepancy is Ω(T 1/2) for any online algorithm.

A sparsifier of a graph G (Benczúr and Karger; Spielman and Teng) is a sparse weighted subgraph G that approximately retains the same cut structure of G. For general graphs, non-trivial sparsification is possible only by using weighted graphs in which different edges have different weights. Even for graphs that admit unweighted sparsifiers (that is, sparsifiers in which all the edge weights are equal to the same scaling factor), there are no known polynomial time algorithms that find such unweighted sparsifiers. We study a weaker notion of sparsification suggested by Oveis Gharan, in which the number of cut edges in each cut (S, S) is not approximated within a multiplicative factor (1+ε), but is, instead, approximated up to an additive term bounded by ε times d·|S| + vol (S), where d is the average degree of the graph and vol (S) is the sum of the degrees of the vertices in S. We provide a probabilistic polynomial time construction of such sparsifiers for every graph, and our sparsifiers have a near-optimal number of edges O(ε-2npolylog (1/ε)). We also provide a deterministic polynomial time construction that constructs sparsifiers with a weaker property having the optimal number of edges O(ε-2n). Our constructions also satisfy a spectral version of the “additive sparsification'' property. Notions of sparsification have also been studied for hypergraphs. Our construction of “additive sparsifiers'' with Oε(n) edges also works for hypergraphs, and provides the first non-trivial notion of sparsification for hypergraphs achievable with O(n) hyperedges when ε and the rank r of the hyperedges are constant. Finally, we provide a new construction of spectral hypergraph sparsifiers, according to the standard definition, with poly (ε-1, r) · n log n hyperedges, improving over the previous spectral construction (Soma and Yoshida) that used Õ(n3) hyperedges even for constant r and ε.

We give a general method for rounding linear programs that combines the commonly used iterated rounding and randomized rounding techniques. In particular, we show that whenever iterated rounding can be applied to a problem with some slack, there is a randomized procedure that returns an integral solution that satisfies the guarantees of iterated rounding and also has concentration properties. We use this to give new results for several classic problems where iterated rounding has been useful.

In this paper, we develop new tools and connections for exponential time approximation. In this setting, we are given a problem instance and an integer $$r>1$$ , and the goal is to design an approximation algorithm with the fastest possible running time. We give randomized algorithms that establish an approximation ratio of (Throughout, $${\tilde{O}}$$ and $$O^*$$ omit $$\hbox {polyloglog} (r)$$ and factors polynomial in the input size, respectively.) The best known time bounds for all problems were $$O^*(2^{n/r})$$ (Bourgeois et al. in Discret Appl Math 159(17):1954–1970, 2011; Cygan et al. in Exponential-time approximation of hard problems, 2008). For maximum independent set and chromatic number, these bounds were complemented by $$\exp (n^{1-o(1)}/r^{1+o(1)})$$ lower bounds (under the Exponential Time Hypothesis (ETH)) (Chalermsook et al. in Foundations of computer science, FOCS, pp. 370–379, 2013; Laekhanukit in Inapproximability of combinatorial problems in subexponential-time. Ph.D. thesis, 2014). Our results show that the naturally-looking $$O^*(2^{n/r})$$ bounds are not tight for all these problems. The key to these results is a sparsification procedure that reduces a problem to a bounded-degree variant, allowing the use of approximation algorithms for bounded-degree graphs. To obtain the first two results, we introduce a new randomized branching rule. Finally, we show a connection between PCP parameters and exponential-time approximation algorithms. This connection together with our independent set algorithm refute the possibility to overly reduce the size of Chan’s PCP (Chan in J. ACM 63(3):27:1–27:32, 2016). It also implies that a (significant) improvement over our result will refute the gap-ETH conjecture (Dinur in Electron Colloq Comput Complex (ECCC) 23:128, 2016; Manurangsi and Raghavendra in A birthday repetition theorem and complexity of approximating dense CSPs, 2016).

We consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most $t$ sets. We give an efficient algorithm that finds a coloring with discrepancy $O((t \log n)^{1/2})$, matching the best known nonconstructive bound for the problem due to Banaszczyk. The previous algorithms only achieved an $O(t^{1/2} \log n)$ bound. The result also extends to the more general Komlós setting and gives an algorithmic $O(\log^{1/2} n)$ bound.

We study the k -server problem in the resource augmentation setting, i.e., when the performance of the online algorithm with k servers is compared to the offline optimal solution with h ≤ k servers. The problem is very poorly understood beyond uniform metrics. For this special case, the classic k -server algorithms are roughly (1+1/ϵ)-competitive when k =(1+ϵ) h , for any ϵ > 0. Surprisingly, however, no o ( h )-competitive algorithm is known even for HSTs of depth 2 and even when k / h is arbitrarily large. We obtain several new results for the problem. First, we show that the known k -server algorithms do not work even on very simple metrics. In particular, the Double Coverage algorithm has competitive ratio Ω ( h ) irrespective of the value of k , even for depth-2 HSTs. Similarly, the Work Function Algorithm, which is believed to be optimal for all metric spaces when k = h , has competitive ratio Ω ( h ) on depth-3 HSTs even if k =2 h . Our main result is a new algorithm that is O (1)-competitive for constant depth trees, whenever k =(1+ϵ) h for any ϵ > 0. Finally, we give a general lower bound that any deterministic online algorithm has competitive ratio at least 2.4 even for depth-2 HSTs and when k / h is arbitrarily large. This gives a surprising qualitative separation between uniform metrics and depth-2 HSTs for the ( h , k )-server problem.

In real-time systems, in addition to the functional correctness recurrent tasks must fulfill timing constraints to ensure the correct behavior of the system. Partitioned scheduling is widely used in real-time systems, i.e., the tasks are statically assigned onto processors while ensuring that all timing constraints are met. The decision version of the problem, which is to check whether the deadline constraints of tasks can be satisfied on a given number of identical processors, has been known NP-complete in the strong sense. Several studies on this problem are based on approximations involving resource augmentation, i.e., speeding up individual processors. This paper studies another type of resource augmentation by allocating additional processors, a topic that has not been explored until recently. We provide polynomial-time algorithms and analysis, in which the approximation factors are dependent upon the input instances. Specifically, the factors are related to the maximum ratio of the period to the relative deadline of a task in the given task set. We also show that these algorithms unfortunately cannot achieve a constant approximation factor for general cases. Furthermore, we prove that the problem does not admit any asymptotic polynomial-time approximation scheme (APTAS) unless P=NP when the task set has constrained deadlines, i.e., the relative deadline of a task is no more than the period of the task.

The generalized k-server problem is a far-reaching extension of the k-server problem with several applications. Here, each server si lies in its own metric space Mi. A request is a k-tuple r = (r1, r2, …, rk) and to serve it, we need to move some server si to the point ri ∊ Mi, and the goal is to minimize the total distance traveled by the servers. Despite much work, no f(k)-competitive algorithm is known for the problem for k > 2 servers, even for special cases such as uniform metrics and lines. Here, we consider the problem in uniform metrics and give the first f(k)-competitive algorithms for general k. In particular, we obtain deterministic and randomized algorithms with competitive ratio k · 2k and O(k3 log k) respectively. Our deterministic bound is based on a novel application of the polynomial method to online algorithms, and essentially matches the long-known lower bound of 2k – 1. We also give a 22O(k)-competitive deterministic algorithm for weighted uniform metrics, which also essentially matches the recent doubly exponential lower bound for the problem.

In the Convex Body Chasing problem, we are given an initial point v0 ∊ ℝd and an online sequence of n convex bodies F1, …, Fn. When we receive Fi, we are required to move inside Fi. Our goal is to minimize the total distance traveled. This fundamental online problem was first studied by Friedman and Linial (DCG 1993). They proved an lower bound on the competitive ratio, and conjectured that a competitive ratio depending only on d is possible. However, despite much interest in the problem, the conjecture remains wide open. We consider the setting in which the convex bodies are nested: Fi ⊃ … ⊃ Fn. The nested setting is closely related to extending the online LP framework of Buchbinder and Naor (ESA 2005) to arbitrary linear constraints. Moreover, this setting retains much of the difficulty of the general setting and captures an essential obstacle in resolving Friedman and Linial's conjecture. In this work, we give a f(d)-competitive algorithm for chasing nested convex bodies in ℝd.

An important result in discrepancy due to Banaszczyk states that for any set of n vectors in ℝm of ℓ2 norm at most 1 and any convex body K in ℝm of Gaussian measure at least half, there exists a ± 1 combination of these vectors which lies in 5K. This result implies the best known bounds for several problems in discrepancy. Banaszczyk’s proof of this result is non-constructive and an open problem has been to give an efficient algorithm to find such a ± 1 combination of the vectors.

We study the Double Coverage (DC) algorithm for the k-server problem in tree metrics in the (h, k)-setting, i.e., when DC with k servers is compared against an offline optimum algorithm with h ≤ k servers. It is well-known that in such metric spaces DC is k-competitive (and thus optimal) for h = k. We prove that even if k > h the competitive ratio of DC does not improve; in fact, it increases slightly as k grows, tending to h + 1. Specifically, we give matching upper and lower bounds of $\frac {k(h+1)}{k+1}$ on the competitive ratio of DC on any tree metric.

We consider the maximum independent set problem on sparse graphs with maximum degree $d$. We show that the Lovász $\vartheta$-function based semidefinite program (SDP) has an integrality gap of $ \widetilde{O}(d/\log^{3/2} d)$, improving on the previous best result of $\widetilde{O}(d/\log d)$. This improvement is based on a new Ramsey-theoretic bound on the independence number of $K_r$-free graphs for large values of $r$. We also show that for stronger SDPs, namely, those obtained using poly$\log(d)$ levels of the ${SA}^{+}$ semidefinite hierarchy, the integrality gap reduces to $\widetilde{O}(d/\log^2 d)$. This matches the best unique-games-based hardness result up to lower-order poly$(\log\log d)$ factors. Finally, we give an algorithmic version of this ${SA}^{+}$-based integrality gap result, albeit using $d$ levels of ${SA}^{+}$, via a coloring algorithm of Johansson.

We present randomized algorithms that solve subset sum and knapsack instances with $n$ items in $O^*(2^{0.86n})$ time, where the $O^*(\cdot)$ notation suppresses factors polynomial in the input size, and polynomial space, assuming random read-only access to exponentially many random bits. These results can be extended to solve binary integer programming on $n$ variables with few constraints in a similar running time. We also show that for any constant $k\geq 2$, random instances of $k$-sum can be solved using $O(n^{k-0.5}\mathrm{polylog}(n))$ time and $O(\log n)$ space, without the assumption of random access to random bits. Underlying these results is an algorithm that determines whether two given lists of length $n$ with integers bounded by a polynomial in $n$ share a common value. Assuming random read-only access to random bits, we show that this problem can be solved using $O(\log n)$ space significantly faster than the trivial $O(n^2)$ time algorithm if no value occurs too often in the same list.

The weighted k-server problem is a natural generalization of the k-server problem where each server has a different weight. We consider the problem on uniform metrics, which corresponds to a natural generalization of paging. Our main result is a doubly exponential lower bound on the competitive ratio of any deterministic online algorithm, that essentially matches the known upper bounds for the problem and closes a large and long-standing gap. The lower bound is based on relating the weighted k-server problem to a certain combinatorial problem and proving a Ramsey-theoretic lower bound for it. This combinatorial connection also reveals several structural properties of low cost feasible solutions to serve a sequence of requests. We use this to show that the generalized Work Function Algorithm achieves an almost optimum competitive ratio, and to obtain new refined upper bounds on the competitive ratio for the case of d different weight classes.

We give a general approach for solving optimization problems on noisy minor free and bounded treewidth graphs, where a fraction of edges are adversarially corrupted. The noisy setting was first considered by Magen and Moharrami and they gave a (1 + ∊)-estimation algorithm for the independent set problem. Later, Chan and Har-Peled designed a local search algorithm that finds a (1 + ∊)-approximate independent set. However, nothing was known regarding other problems in the noisy setting. Our main contribution is a general LP-based framework that yields (1 + ∊)-approximation algorithms for noisy MAX-k-CSPs.

We study the k-server problem in the resource augmentation setting i.e., when the performance of the online algorithm with k servers is compared to the offline optimal solution with H ≤ k servers. The problem is very poorly understood beyond uniform metrics. For this special case, the classic k-server algorithms are roughly (1 + 1/∊)-competitive when k = (1 + ∊)h, for any ∊ > 0. Surprisingly however, no o(h)- competitive algorithm is known even for HSTs of depth 2 and even when k/h is arbitrarily large. We obtain several new results for the problem. First we show that the known k-server algorithms do not work even on very simple metrics. In particular, the Double Coverage algorithm has competitive ratio O(h) irrespective of the value of k, even for depth-2 HSTs. Similarly the Work Function Algorithm, that is believed to be optimal for all metric spaces when k = h, has competitive ratio O(h) on depth-3 HSTs even if k = 2h. Our main result is a new algorithm that is O(1)-competitive for constant depth trees, whenever k = (1 + ∊)h for any ∊ > 0. Finally, we give a general lower bound that any deterministic online algorithm has competitive ratio at least 2.4 even for depth-2 HSTs and when k/h is arbitrarily large. This gives a surprising qualitative separation between uniform metrics and depth-2 HSTs for the (h, k)-server problem, and gives the strongest known lower bound for the problem on general metrics.

The partial coloring method is one of the most powerful and widely used method in combinatorial discrepancy problems. However, in many cases it leads to sub-optimal bounds as the partial coloring step must be iterated a logarithmic number of times, and the errors can add up in an adversarial way.

We present randomized algorithms that solve Subset Sum and Knapsack instances with n items in O*(20.86n) time, where the O*(·) notation suppresses factors polynomial in the input size, and polynomial space, assuming random read-only access to exponentially many random bits. These results can be extended to solve Binary Linear Programming on n variables with few constraints in a similar running time. We also show that for any constant k≥ 2, random instances of k-Sum can be solved using O(nk-0.5(n)) time and O(logn) space, without the assumption of random access to random bits.

We consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most t sets. We give an efficient algorithm that finds a coloring with discrepancy O((t log n)1/2), matching the best known non-constructive bound for the problem due to Banaszczyk. The previous algorithms only achieved an O(t1/2log n) bound. Our result also extends to the more general Komlós setting and gives an algorithmic O(log1/2n) bound.

We study the d-dimensional vector bin packing problem, a well-studied generalization of bin packing arising in resource allocation and scheduling problems. Here we are given a set of d-dimensional vectors v1, …, vn in [0, 1]d, and the goal is to pack them into the least number of bins so that for each bin B, the sum of the vectors in it is at most 1 in every dimension, i.e., . For the 2-dimensional case we give an asymptotic approximation guarantee of 1 + ln(1.5) + ∊ ≈ (1.405 + ∊), improving upon the previous bound of 1 + ln 2 + ∊ ≈ (1.693 + ∊). We also give an almost tight (1.5+ ∊) absolute approximation guarantee, improving upon the previous bound of 2 [23]. For the d-dimensional case, we get a guarantee, improving upon the previous (1 + ln d + ∊) guarantee [2]. Here (1 + ln d) was a natural barrier as rounding-based algorithms can not achieve better than d approximation. We get around this by exploiting various structural properties of (near)-optimal packings, and using multi-objective multi-budget matching based techniques and expanding the Round & Approx framework to go beyond rounding-based algorithms. Along the way we also prove several results that could be of independent interest.

We consider the problem of scheduling jobs on unrelated machines so as to minimize the sum of weighted completion times. Our main result is a (3/2-c)-approximation algorithm for some fixed c>0, improving upon the long-standing bound of 3/2. To do this, we first introduce a new lift-and-project based SDP relaxation for the problem. This is necessary as the previous convex programming relaxations have an integrality gap of 3/2. Second, we give a new general bipartite-rounding procedure that produces an assignment with certain strong negative correlation properties.

We consider the Vector Scheduling problem, a natural generalization of the classical makespan minimization problem to multiple resources. Here, we are given n jobs, represented as d-dimensional vectors in $$[0,1]^d$$ , and m identical machines, and the goal is to assign the jobs to machines such that the maximum load of each machine over all the coordinates is at most 1. For fixed d, the problem admits an approximation scheme, and the best known running time is $$n^{f(\epsilon ,d)}$$ where $$f(\epsilon ,d) = (1/\epsilon )^{\tilde{O}(d)}$$ ( $$\tilde{O}$$ suppresses polylogarithmic terms in d). In particular, the dependence on d is double exponential. In this paper we show that a double exponential dependence on d is necessary, and give an improved algorithm with essentially optimal running time. Specifically, we let $$\exp (x)$$ denote $$2^x$$ and show that: (1) For any $$\epsilon <1$$ , there is no $$(1+\epsilon )$$ -approximation with running time $$\exp \left( o(\lfloor 1/\epsilon \rfloor ^{d/3})\right) $$ unless the Exponential Time Hypothesis fails. (2) No $$(1+\epsilon )$$ -approximation with running time $$\exp \left( \lfloor 1/\epsilon \rfloor ^{o(d)}\right) $$ exists, unless NP has subexponential time algorithms. (3) Similar lower bounds also hold even if $$\epsilon m$$ extra machines are allowed (i.e. with resource augmentation), for sufficiently small $$\epsilon >0$$ . (4) We complement these lower bounds with a $$(1+\epsilon )$$ -approximation that runs in time $$\exp \left( (1/\epsilon )^{O(d \log \log d)}\right) + nd$$ . This gives the first efficient approximation scheme (EPTAS) for the problem.

We consider the online problem of minimizing the maximum flow-time on related machines. This is a natural generalization of the extensively studied makespan minimization problem to the setting where jobs arrive over time. Interestingly, natural algorithms such as Greedy or Slow-fit that work for the simpler identical machines case or for makespan minimization on related machines, are not O(1)-competitive. Our main result is a new O(1)-competitive algorithm for the problem. Previously, O(1)-competitive algorithms were known only with resource augmentation, and in fact no O(1) approximation was known even in the offline case.

We consider a natural online optimization problem set on the real line. The state of the online algorithm at each integer time is a location on the real line. At each integer time, a convex function arrives online. In response, the online algorithm picks a new location. The cost paid by the online algorithm for this response is the distance moved plus the value of the function at the final destination. The objective is then to minimize the aggregate cost over all time. The motivating application is rightsizing power-proportional data centers. We give a 2-competitive algorithm for this problem. We also give a 3-competitive memoryless algorithm, and show that this is the best competitive ratio achievable by a deterministic memoryless algorithm. Finally we show that this online problem is strictly harder than the standard ski rental problem.

We consider the maximum independent set problem on sparse graphs with maximum degree d. The best known result for the problem is an SDP based O(d log log d/log d) approximation due to Halperin. It is also known that no o(d/ log2 d) approximation exists assuming the Unique Games Conjecture. We show the following two results:

We consider the maximum independent set problem on graphs with maximum degree d. We show that the integrality gap of the Lovasz Theta function-based SDP has an integrality gap of O~(d/log3/2 d). This improves on the previous best result of O~(d/log d), and narrows the gap of this basic SDP to the integrality gap of O~(d/log2 d) recently shown for stronger SDPs, namely those obtained using poly log(d) levels of the SA+ semidefinite hierarchy. The improvement comes from an improved Ramsey-theoretic bound on the independence number of Kr-free graphs for large values of r.

We consider some classical flow-time minimization problems in the unrelated machines setting. In this setting, there is a set of m machines and a set of n jobs, and each job j has a machine dependent processing time of pij on machine i. The flow-time of a job is the amount of time the job spends in a system (its completion time minus its arrival time), and is one of the most natural measure of quality of service. We show the following two results: an $O(min(log2 n, log n log P)) approximation algorithm for minimizing the total flow-time, and an O(log n) approximation for minimizing the maximum flow-time. Here P is the ratio of maximum to minimum job size. These are the first known poly-logarithmic guarantees for both the problems.

We give the first polylogarithmic-competitive randomized online algorithm for the k -server problem on an arbitrary finite metric space. In particular, our algorithm achieves a competitive ratio of Õ(log 3 n log 2 k ) for any metric space on n points. Our algorithm improves upon the deterministic (2 k -1)-competitive algorithm of Koutsoupias and Papadimitriou [Koutsoupias and Papadimitriou 1995] for a wide range of n .

We study a basic resource allocation problem that arises in cloud computing environments. The physical network of the cloud is represented as a graph with vertices representing servers and edges corresponding to communication links. A workload is a set of processes with processing requirements and mutual communication requirements. The workloads arrive and depart over time, and the resource allocator must map each workload upon arrival to the physical network. We consider the objective of minimizing the congestion. We show that solving a subproblem (\sf SingleMap) about mapping a single workload to the physical graph essentially suffices for solving the general problem. In particular, an $\alpha$-approximation algorithm for \sf SingleMap gives an $O(\alpha \log nD)$ competitive algorithm for the general problem, where $n$ is the number of nodes in the physical network and $D$ is the maximum to minimum workload duration ratio. We then consider the \sf SingleMap problem for two natural classes of workloads, namely depth-$d$ trees and complete-graph workloads. For depth-$d$ trees, we give an $n^{O(d)}$ time $O(d^2 \log (nd))$-approximation algorithm based on a strong LP relaxation inspired by the Sherali--Adams hierarchy. For complete graphs, we give a polylogarithmic approximation algorithm using Räcke decompositions.

Iterated rounding is a relatively recent technique in algorithm design, that despite its simplicity has led to several remarkable new results and also simpler proofs of many previous results. We will briefly survey some applications of the method, including some recent developments and giving a high level overview of the ideas.

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.

We study the two-dimensional bin packing problem with and without rotations. Here we are given a set of two-dimensional rectangular items I and the goal is to pack these into a minimum number of unit square bins. We consider the orthogonal packing case where the edges of the items must be aligned parallel to the edges of the bin. Our main result is a 1.405-approximation for two-dimensional bin packing with and without rotation, which improves upon a recent 1.5 approximation due to Jansen and Prädel. We also show that a wide class of rounding based algorithms cannot improve upon the factor of 1.5.

We study graph partitioning problems from a min-max perspective, in which an input graph on $n$ vertices should be partitioned into $k$ parts, and the objective is to minimize the maximum number of edges leaving a single part. The two main versions we consider are where the $k$ parts need to be of equal size, and where they must separate a set of $k$ given terminals. We consider a common generalization of these two problems, and design for it an $O(\sqrt{\log n\log k})$ approximation algorithm. This improves over an $O(\log^2 n)$ approximation for the second version due to Svitkina and Tardos [Min-max multiway cut, in APPROX-RANDOM, 2004, Springer, Berlin, 2004], and roughly $O(k\log n)$ approximation for the first version that follows from other previous work. We also give an $O(1)$ approximation algorithm for graphs that exclude any fixed minor. Our algorithm uses a new procedure for solving the small-set expansion problem. In this problem, we are given a graph $G$ and the goal is to find a nonempty set $S\subseteq V$ of size $|S| \leq \rho n$ with minimum edge expansion. We give an $O(\sqrt{\log{n}\log{(1/\rho)}})$ bicriteria approximation algorithm for small-set expansion in general graphs, and an improved factor of $O(1)$ for graphs that exclude any fixed minor.

We consider the following general scheduling problem. The input consists of $n$ jobs, each with an arbitrary release time, size, and monotone function specifying the cost incurred when the job is completed at a particular time. The objective is to find a preemptive schedule of minimum aggregate cost. This problem formulation is general enough to include many natural scheduling objectives, such as total weighted flow time, total weighted tardiness, and sum of flow time squared. We give an $O(\log \log P )$ approximation for this problem, where $P$ is the ratio of the maximum to minimum job size. We also give an $O(1)$ approximation in the special case of identical release times. These results are obtained by reducing the scheduling problem to a geometric capacitated set cover problem in two dimensions.

We consider the unsplittable flow problem on a line. In this problem, we are given a set of n tasks, each specified by a start time s i , an end time t i , a demand d i > 0, and a profit p i > 0. A task, if accepted, requires d i units of “bandwidth” from time s i to t i and accrues a profit of p i . For every time t , we are also specified the available bandwidth c t , and the goal is to find a subset of tasks with maximum profit subject to the bandwidth constraints. We present the first polynomial time O (log n ) approximation algorithm for this problem. This significantly advances the state of the art, as no polynomial time o ( n ) approximation was known previously. Previous results for this problem were known only in more restrictive settings; in particular, either the instance satisfies the so-called “no-bottleneck” assumption: max i d i ≤ min t c t , or the ratio of both maximum to minimum demands and maximum to minimum capacities are polynomially (or quasi-polynomially) bounded in n . Our result, on the other hand, does not require these assumptions. Our algorithm is based on a combination of dynamic programming and rounding a natural linear programming relaxation for the problem. While there is an Ω( n ) integrality gap known for this LP relaxation, our key idea is to exploit certain structural properties of the problem to show that instances that are bad for the LP can in fact be handled using dynamic programming.

In the classical broadcast scheduling problem , there are n pages stored at a server, and requests for these pages arrive over time. Whenever a page is broadcast, it satisfies all outstanding requests for that page. The objective is to minimize average flow time of the requests. For any ϵ > 0, we give a (1+ϵ)-speed O (1/ϵ 3 )-competitive online algorithm for broadcast scheduling. This improves over the recent breakthrough result of Im and Moseley [2010], where they obtained a (1+ϵ)-speed O (1/ϵ 11 )-competitive algorithm. Our algorithm and analysis are considerably simpler than Im and Moseley [2010]. More importantly, our techniques also extend to the general setting of nonuniform page sizes and dependent requests . This is the first scalable algorithm for broadcast scheduling with varying size pages and resolves the main open question from Im and Moseley [2010].

We consider the problem of determining mn, the number of matroids on n elements. The best known lower bound on mn is due to Knuth (1974) who showed that log log mn is at least . On the other hand, Piff (1973) showed that log log mn ≤ n − log n + log log n + O(1), and it has been conjectured since that the right answer is perhaps closer to Knuth's bound. We show that this is indeed the case, and prove an upper bound on log log mn that is within an additive 1 + o(1) term of Knuth's lower bound. Our proof is based on using some structural properties of non-bases in a matroid together with some properties of independent sets in the Johnson graph to give a compressed representation of matroids.

In the three-dimensional (3D) strip packing problem, we are given a set of 3D rectangular items and a 3D box $B$. The goal is to pack all the items in $B$ such that the height of the packing is minimized. We consider the most basic version of the problem, where the items must be packed with their edges parallel to the edges of $B$ and cannot be rotated. Building upon Caprara's work for the two-dimensional (2D) bin packing problem, we obtain an algorithm that, given any $\epsilon>0$, achieves an approximation of $T_{\infty}+\epsilon\approx1.69103+\epsilon$, where $T_{\infty}$ is the well-known number that occurs naturally in the context of bin packing. Our key idea is to establish a connection between bin packing solutions for an arbitrary instance $I$ and the strip packing solutions for the corresponding instance obtained from $I$ by applying the harmonic transformation to certain dimensions. Based on this connection, we also give a simple alternate proof of the $T_{\infty}+\epsilon$ approximation for 2D bin packing due to Caprara. In particular, we show how his result follows from a simple modification of the asymptotic approximation scheme for 2D strip packing due to Kenyon and Rémila.

This article initiates a theoretical investigation into online scheduling problems with speed scaling where the allowable speeds may be discrete, and the power function may be arbitrary, and develops algorithmic analysis techniques for this setting. We show that a natural algorithm, which uses Shortest Remaining Processing Time for scheduling and sets the power to be one more than the number of unfinished jobs, is 3-competitive for the objective of total flow time plus energy. We also show that another natural algorithm, which uses Highest Density First for scheduling and sets the power to be the fractional weight of the unfinished jobs, is a 2-competitive algorithm for the objective of fractional weighted flow time plus energy.

Mutual Exclusion is a fundamental problem in distributed computing, and the problem of proving upper and lower bounds on the RMR complexity of this problem has been extensively studied. Here, we give matching lower and upper bounds on how RMR complexity trades off with space. Two implications of our results are that constant RMR complexity is impossible with subpolynomial space and subpolynomial RMR complexity is impossible with constant space for cache-coherent multiprocessors, regardless of how strong the hardware synchronization operations are.

We study the weighted version of the classic online paging problem where there is a weight (cost) for fetching each page into the cache. We design a randomized O (log k )-competitive online algorithm for this problem, where k is the cache size. This is the first randomized o ( k )-competitive algorithm and its competitive ratio matches the known lower bound for the problem, up to constant factors. More generally, we design an O (log( k /( k − h + 1)))-competitive online algorithm for the version of the problem where the online algorithm has cache size k and it is compared to an optimal offline solution with cache size h ≤ k . Our solution is based on a two-step approach. We first obtain an O (log k )-competitive fractional algorithm based on an online primal-dual approach. Next, we obtain a randomized algorithm by rounding in an online manner the fractional solution to a probability distribution on the possible cache states. We also give an online primal-dual randomized O (log N )-competitive algorithm for the Metrical Task System problem (MTS) on a weighted star metric on N leaves.

We consider online algorithms for the generalized caching problem. Here we are given a cache of size k and pages with arbitrary sizes and fetching costs. Given a request sequence of pages, the goal is to minimize the total cost of fetching the pages into the cache. Our main result is an online algorithm with competitive ratio $O(\log^2k)$, which gives the first $o(k)$ competitive algorithm for the problem. We also give improved $O(\log k)$-competitive algorithms for the special cases of the bit model and fault model, improving upon the previous $O(\log^2k)$ guarantees due to Irani [Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 701–710]. Our algorithms are based on an extension of the online primal-dual framework introduced by Buchbinder and Naor [Math. Oper. Res., 34 (2009), pp. 270–286] and involve two steps. First, we obtain an $O(\log k)$-competitive fractional algorithm based on solving online an LP formulation strengthened with exponentially many knapsack cover constraints. Second, we design a suitable online rounding procedure to convert this online fractional algorithm into a randomized algorithm. Our techniques provide a unified framework for caching algorithms and are substantially simpler than those previously used.

We give the first polylogarithmic-competitive randomized algorithm for the k-server problem on an arbitrary finite metric space. In particular, our algorithm achieves a competitive ratio of Õ(log3n log2k) for any metric space on n points. This improves upon the (2k-1)-competitive algorithm of Koutsoupias and Papadimitriou (J. ACM 1995) whenever n is sub-exponential in k.

We study graph partitioning problems from a min-max perspective, in which an input graph on n vertices should be partitioned into k parts, and the objective is to minimize the maximum number of edges leaving a single part. The two main versions we consider are: (i) the k parts need to be of equal size, and (ii) the parts must separate a set of k given terminals. We consider a common generalization of these two problems, and design for it an O(√log n log k)-approximation algorithm. This improves over an O(log2n) approximation for the second version due to Svitkina and Tardos, and roughly O(k log n) approximation for the first version that follows from other previous work. We also give an improved O(1)-approximation algorithm for graphs that exclude any fixed minor. Our algorithm uses a new procedure for solving the Small Set Expansion problem. In this problem, we are given a graph G and the goal is to find a non-empty subset S of V of size at most pn with minimum edge-expansion. We give an O(√log n log (1/p)) bicriteria approximation algorithm for the general case of Small Set Expansion and O(1) approximation algorithm for graphs that exclude any fixed minor.

We study a basic resource allocation problem that arises in cloud computing environments. The physical network of the cloud is represented as a graph with vertices denoting servers and edges corresponding to communication links. A workload is a set of processes with processing requirements and mutual communication requirements. The workloads arrive and depart over time, and the resource allocator must map each workload upon arrival to the physical network. We consider the objective of minimizing the congestion.

Given a set system (V, S), V = {1,..., n} and S = {S1,...,Sm}, the minimum discrepancy problem is to find a 2-coloring X : V → {-1,+1}, such that each set is colored as evenly as possible, i.e. find X to minimize maxj∈|m]Σi∈sjX(i)|· In this paper we give the first polynomial time algorithms for discrepancy minimization that achieve bounds similar to those known existentially using the so-called Entropy Method. We also give a first approximation-like result for discrepancy. Specifically we give efficient randomized algorithms to: 1) Construct an O(n1/2) discrepancy coloring for general sets systems when m = O(n), matching the celebrated result of Spencer [17] up to O(1) factors. More generally, for m ≥ n, we obtain a discrepancy of O(n1/2log(2m/n)). 2) Construct a coloring with discrepancy O(t1/2log n), if each element lies in at most t sets. This matches the (nonconstructive) result of Srinivasan [19]. 3) Construct a coloring with discrepancy O(λlog(ram)), where λ is the hereditary discrepancy of the set system. The main idea in our algorithms is to produce a coloring over time by letting the color of the elements perform a random walk (with tiny increments) starting from 0 until they reach ±1. At each step the random hops for various elements are correlated by a solution to a semidefinite program, where this program is determined by the current state and the entropy method.

We consider the following general scheduling problem: The input consists of n jobs, each with an arbitrary release time, size, and a monotone function specifying the cost incurred when the job is completed at a particular time. The objective is to find a preemptive schedule of minimum aggregate cost. This problem formulation is general enough to include many natural scheduling objectives, such as weighted flow, weighted tardiness, and sum of flow squared. The main contribution of this paper is a randomized polynomial-time algorithm with an approximation ratio O(log log n P), where P is the maximum job size. We also give an O(1) approximation in the special case when all jobs have identical release times. Initially, we show how to reduce this scheduling problem to a particular geometric set-cover problem. We then consider a natural linear programming formulation of this geometric set-cover problem, strengthened by adding knapsack cover inequalities, and show that rounding the solution of this linear program can be reduced to other particular geometric set-cover problems. We then develop algorithms for these sub-problems using the local ratio technique, and Varadarajan's quasi-uniform sampling technique. This general algorithmic approach improves the best known approximation ratios by at least an exponential factor (and much more in some cases) for essentially all of the nontrivial common special cases of this problem. We believe that this geometric interpretation of scheduling is of independent interest.

Recently, Coté et al. [10] proposed an approach for solving the k-server problem on Hierchically Separated Trees (HSTs). In particular, they define a problem on a uniform metric, and show that if an algorithm with a certain refined guarantee exists for it, then one can obtain polylogarithmic (in diameter) competitive factors for the k-server problem on HSTs by solving this problem recursively. By designing such an algorithm for a two point metric, they obtained a logarithmic competitive algorithm for well-separated binary HSTs. Extending their result to uniform metrics on arbitrarily many points would imply a poly-logarithmic competitive algorithm for k-server on general HSTs (and hence general metrics) and is thus of major interest. Here, we design such an algorithm for any uniform metric, provided the instance satisfies a certain “convexity” property. Even though this does not give a result for k-server, convexity seems to be a very natural property, and we give evidence that instances arising in the Coté et al. [10] reduction from k-server essentially possess this property, suggesting that this might be a promising approach. Already, our setting is general enough to model the finely competitive paging problem proposed by Blum et al. [4], who motivated it as a first step towards achieving a polylog(k) competitive algorithm for k-server. Our result implies an r + O(log k)-competitive algorithm for finely competitive paging, resolving the main open problem of [4]. Our results are based on an extension of the primal-dual framework for online algorithms developed by Buchbinder and Naor [7]. The original approach works for problems whose offline version can be expressed as a packing or a covering linear program, possibly with box constraints. The online nature of the problem is modeled by revealing the constraints one by one and the requirement that variables can only be increased over time. Here, we consider more general types of constraints, where terms can be both positive and negative. Moreover, we allow the variables to both increase and decrease. This versatility allows us to model problems such as predicting with expert advice, which could not be modeled earlier. To show the simplicity and generality of this approach, we give an alternate O(log k)-competitive algorithm for weighted paging with a very simple proof. We also give an alternate primal-dual approach to design regret minimization algorithms for the problem of online prediction with expert advice. Our results suggest the possibility of a more general primal-dual framework for online problems beyond covering and packing LPs.

Consider the following generalized min-sum set cover or multiple intents re-ranking problem proposed by Azar et al. (STOC 2009). We are given a universe of elements and a collection of subsets, with each set S having a covering requirement of K(S). The objective is to pick one element at a time such that the average covering time of the sets is minimized, where the covering time of a set S is the first time at which K(S) elements from it have been selected. There are two well-studied extreme cases of this problem: (i) when K(S) = 1 for all sets, we get the min-sum set cover problem, and (ii) when K(S) = |S| for all sets, we get the minimum-latency set cover problem. Constant factor approximations are known for both these problems. In their paper, Azar et al. considered the general problem and gave a logarithmic approximation algorithm for it. In this paper, we improve their result and give a simple randomized constant factor approximation algorithm for the generalized min-sum set cover problem.

Often server systems do not implement the best known algorithms for optimizing average Quality of Service (QoS) out of concern that these algorithms may be insufficiently fair to individual jobs. The standard method for balancing average QoS and fairness is to optimize the $\ell_p$ norm, $1

We study the following problem related to pricing over time. Assume there is a collection of bidders, each of whom is interested in buying a copy of an item of which there is an unlimited supply. Every bidder is associated with a time interval over which the bidder will consider buying a copy of the item, and a maximum value the bidder is willing to pay for the item. On every time unit, the seller sets a price for the item. The seller's goal is to set the prices so as to maximize revenue from the sale of copies of items over the time period. In the first model considered, we assume that all bidders are impatient , that is, bidders buy the item at the first time unit within their bid interval that they can afford the price. To the best of our knowledge, this is the first work that considers this model. In the offline setting, we assume that the seller knows the bids of all the bidders in advance. In the online setting we assume that at each time unit the seller only knows the values of the bids that have arrived before or at that time unit. We give a polynomial time offline algorithm and prove upper and lower bounds on the competitiveness of deterministic and randomized online algorithms, compared with the optimal offline solution. The gap between the upper and lower bounds is quadratic. We also consider the envy-free model in which bidders are sold the item at the minimum price during their bid interval, as long as it is not over their limit value. We prove tight bounds on the competitiveness of deterministic online algorithms for this model, and upper and lower bounds on the competitiveness of randomized algorithms with quadratic gap. The lower bounds for the randomized case in both models use a novel general technique.

For arbitrarily small constants epsilon, delta ¿.¿ > 0, we present a long code test with one free bit, completeness 1-epsilon and soundness delta. Using the test, we prove the following two inapproximability results:1. Assuming the Unique Games Conjecture of Khot, given an n-vertex graph that has two disjoint independent sets of size (1/2-¿)n each, it is NP-hard to find an independent set of size delta n.2. Assuming a (new) stronger version of the Unique Games Conjecture, the scheduling problem of minimizing weighted completion time with precedence constraints is inapproximable within factor 2-¿.

We present new combinatorial algorithms for Boolean matrix multiplication (BMM) and preprocessing a graph to answer independent set queries. We give the first asymptotic improvements on combinatorial algorithms for dense BMM in many years, improving on the "Four Russians'' O(n3/(w log n)) bound for machine models with word size w. (For a pointer machine, we can set w = log n.) The algorithms utilize notions from Regularity Lemmas for graphs in a novel way. 1) We give two randomized combinatorial algorithms for BMM. The first algorithm is essentially a reduction from BMM to the Triangle Removal Lemma}. The best known bounds for the Triangle Removal Lemma only imply an O((n3log ?)/(?w log n)\right) time algorithm for BMM where ? = (log*n)?for some ? > 0, but improvements on the Triangle Removal Lemma would yield corresponding runtime improvements. The second algorithm applies the Weak Regularity Lemma of Frieze and Kannan along with several information compression ideas, running in O(n3(log log n)2/(log n)9/4) time with probability exponentially close to 1. When w ? log n, it can be implemented in O(n3(log log n)2/(w log n)7/6)) time. Our results immediately imply improved combinatorial methods for CFG parsing, detecting triangle-freeness, and transitive closure. 2)Using Weak Regularity, we also give an algorithm for answering queries of the form is S ? V an independent set? in a graph. Improving on prior work, we show how to randomly preprocess a graph in O(n2+?}) time (for all ? > 0) so that with high probability, all subsequent batches of log n independent set queries can be answered deterministically in O(n2(log log n)2/((log n)5/4)) time. When w ? log n, w queries can be answered in O(n2(log log n)2/((log n)7/6))\right) time. In addition to its nice applications, this problem is interesting in that it is not known how to do better than O(n2) using "algebraic'' methods.

We consider the classic online scheduling problem of minimizing the total weighted flow time on a single machine with preemptions. Here, each job j has an arbitrary arrival time rj, weight wj and size pj, and given a schedule its flow time is defined as the duration of time since its arrival until it completes its service requirement. The first non-trivial algorithms with poly-logarithmic competitive ratio for this problem were obtained relatively recently, and it was widely believed that the problem admits a constant factor competitive algorithm. In this paper, we show an ω(1) lower bound on the competitive ratio of any deterministic online algorithm. Our result is based on a gap amplification technique for online algorithms. Starting with a trivial lower bound of 1, we give a procedure to improve the lower bound sequentially, while ensuring at each step that the size of the instance increases relatively modestly.

All of the theoretical speed scaling research to date has assumed that the power function, which expresses the power consumption P as a function of the processor speed s, is of the form P = sα, where α > 1 is some constant. Motivated in part by technological advances, we initiate a study of speed scaling with arbitrary power functions. We consider the problem of minimizing the total flow plus energy. Our main result is a (3+∊)-competitive algorithm for this problem, that holds for essentially any power function. We also give a (2 + ∊)-competitive algorithm for the objective of fractional weighted flow plus energy. Even for power functions of the form sα, it was not previously known how to obtain competitiveness independent of α for these problems. We also introduce a model of allowable speeds that generalizes all known models in the literature.

We consider the unsplittable flow problem on a line. In this problem, we are given a set of n tasks, each specified by a start time si, an end time ti, a demand di > 0, and a profit pi > 0. A task, if accepted, requires di units of “bandwidth” from time si to ti and accrues a profit of pi. For every time t, we are also specified the available bandwidth ct, and the goal is to find a subset of tasks with maximum profit subject to the bandwidth constraints. In this paper, we present the first polynomial-time O(log n)-approximation algorithm for this problem. No polynomial-time o(n)-approximation was known prior to this work. Previous results for this problem were known only in more restrictive settings, in particular, either if the given instance satisfies the so-called “no-bottleneck” assumption: maxi di ≤ mint ct, or else if the ratio of the maximum to the minimum demands and ratio of the maximum to the minimum capacities are polynomially (or quasi-polynomially) bounded in n. Our result, on the other hand, does not require any of these assumptions. Our algorithm is based on a combination of dynamic programming and rounding a natural linear programming relaxation for the problem. While there is an Ω(n) integrality gap known for this LP relaxation, our key idea is to exploit certain structural properties of the problem to show that instances that are bad for the LP can in fact be handled using dynamic programming.

In this paper we introduce a new general approximation method for set covering problems, based on the combination of randomized rounding of the (near-) optimal solution of the linear programming (LP) relaxation, leading to a partial integer solution and the application of a well-behaved approximation algorithm to complete this solution. If the value of the solution returned by the latter can be bounded in a suitable way, as is the case for the most relevant generalizations of bin packing, the method leads to improved approximation guarantees, along with a proof of tighter integrality gaps for the LP relaxation. For d-dimensional vector packing, we obtain a polynomial-time randomized algorithm with asymptotic approximation guarantee arbitrarily close to $\ln d + 1$. For $d=2$, this value is $1.693\dots$; i.e., we break the natural 2 “barrier” for this case. Moreover, for small values of d this is a notable improvement over the previously known $O(\ln d)$ guarantee by Chekuri and Khanna [SIAM J. Comput., 33 (2004), pp. 837–851]. For two-dimensional bin packing with and without rotations, we obtain polynomial-time randomized algorithms with asymptotic approximation guarantee $1.525\dots$, improving upon previous algorithms with asymptotic performance guarantees arbitrarily close to 2 by Jansen and van Stee [On strip packing with rotations, in Proceedings of the 37th Annual ACM Symposium on the Theory of Computing, 2005, pp. 755–761] for the problem with rotations and $1.691\ldots$ by Caprara [Math. Oper. Res., 33 (2008), pp. 203–215] for the problem without rotations. The previously unknown key property used in our proofs follows from a retrospective analysis of the implications of the landmark bin packing approximation scheme by Fernandez de la Vega and Lueker [Combinatorica, 1 (1981), pp. 349–355]. We prove that their approximation scheme is “subset oblivious,” which leads to numerous applications.

We present polynomial-time approximation algorithms for some degree-bounded directed network design problems. Our main result is for intersecting supermodular connectivity requirements with degree bounds: given a directed graph $G=(V,E)$ with nonnegative edge-costs, a connectivity requirement specified by an intersecting supermodular function f, and upper bounds $\{a_v,b_v\}_{v\in V}$ on in-degrees and out-degrees of vertices, find a minimum-cost f-connected subgraph of G that satisfies the degree bounds. We give a bicriteria approximation algorithm for this problem using the natural LP relaxation and show that our guarantee is the best possible relative to this LP relaxation. We also obtain similar results for the (more general) class of crossing supermodular requirements. In the absence of edge-costs, our result gives the first additive $O(1)$-approximation guarantee for degree-bounded intersecting/crossing supermodular connectivity problems. We also consider the minimum crossing spanning tree problem: Given an undirected edge-weighted graph G, edge-subsets $\{E_i\}_{i=1}^k$, and nonnegative integers $\{b_i\}_{i=1}^k$, find a minimum-cost spanning tree (if it exists) in G that contains at most $b_i$ edges from each set $E_i$. We obtain a $+(r-1)$ additive approximation for this problem, when each edge lies in at most r sets. A special case of this problem is the degree-bounded minimum spanning tree, and our techniques give a substantially shorter proof of the recent $+1$ approximation of Singh and Lau [in Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2007, pp. 661–670].

Intel's SpeedStep and AMD's PowerNOW technologies allow the Windows XP operating system to dynamically change the speed of the processor to prolong battery life. In this setting, the operating system must not only have a job selection policy to determine which job to run, but also a speed scaling policy to determine the speed at which the job will be run. We give an online speed scaling algorithm that is $O(1)$-competitive for the objective of weighted flow time plus energy. This algorithm also allows us to efficiently construct an $O(1)$-approximate schedule for minimizing weighted flow time subject to an energy constraint.

We introduce Zen, a new resource allocation framework that assigns application components to node clusters to achieve high availability for partial-fault tolerant (PFT) applications. These applications have the characteristic that under partial failures, they can still produce useful output though the output quality may be reduced. Thus, the primary goal of resource allocation for PFT applications is to prevent, delay, or minimize the impact of failures on the application output quality. This paper is the first to approach this resource allocation problem from a theoretical perspective, and obtains a series of results regarding component assignments that provide the highest service availability under the constraints imposed by the application data flow graph and the hosting clusters. We show that (1) even simple versions of this resource allocation problem are NP-Hard, (2) a 2-approximate polynomial-time algorithm works for tree topologies, and (3) a simple greedy component placement performs well in practice for general application topologies. We implement a system prototype to study the application availability achieved by Zen compared to failure-oblivious placement, replication, and Zen+replication. Our experimental results show that three PFT applications achieve significant data output quality and availability benefits using Zen.

This paper describes how we can use existing mobile technology to track the vehicle. Here the embedded system along with the mobile is used to prevent the vehicle from being stolen and also if the vehicle is stolen then its location can be tracked. Mobile technology is the fastest growing communication mode. In today’s mobile technology we all are acquainted with Short Message Service (SMS). In this paper we have used this service along with the embedded system for fulfillment of our purpose. The technology used in this paper is the combination of hardware (motors, Relay and embedded parts) and software (AT commands and program for microcontroller). This paper elaborates how we have used the Protocol Data Unit (PDU) format of SMS with the help of microcontroller to control and track the experimental setup. Our embedded system can be fixed in any vehicle to control and track the vehicle just by sending SMS by authorized persons. This system is cost effective, reliable, user friendly and can be used in remote areas.

We consider online algorithms for the generalized caching problem. Here we are given a cache of size k and pages with arbitrary sizes and fetching costs. Given a request sequence of pages, the goal is to minimize the total cost of fetching the pages into the cache. We give an online algorithm with competitive ratio O(log2k), which is the first algorithm for the problem with competitive ratio sublinear in k. We also give improved O(log k)-competitive algorithms for the special cases of the Bit Model and Fault model. In the Bit Model, the fetching cost is proportional to the size of the page and in the Fault model all fetching costs are uniform. Previously, an O(log2 k)-competitive algorithm due to Irani [14] was known for both of these models. Our algorithms are based on an extension of the primal-dual framework for online algorithms which was developed by Buchbinder and Naor [7]. We first generate an O(log k)-competitive fractional algorithm for the problem. This is done by using a strengthened LP formulation with knapsack-cover constraints, where exponentially many constraints are added upon arrival of a new request. Second, we round online the fractional solution and obtain a randomized online algorithm. Our techniques provide a unified framework for caching algorithms and are substantially simpler than those previously used.

We present polynomial-time approximation algorithms for some degree-bounded directed network design problems. Our main result is for intersecting supermodular connectivity with degree bounds: given a directed graph G=(V,E) with non-negative edge-costs, a connectivity requirement specified by an intersecting supermodular function f, and upper bounds av, bvv∈ V on in-degrees and out-degrees of vertices, find a minimum-cost f-connected subgraph of G that satisfies the degree bounds. We give a bicriteria approximation algorithm that for any 0 ≤ ε ≤ 1/2, computes an f-connected subgraph with in-degrees at most ⌈ av/1-ε ⌉ + 4, out-degrees at most ⌈ bv/1-ε ⌉ + 4, and cost at most 1/ε times the optimum. This includes, as a special case, the minimum-cost degree-bounded arborescence problem. We also obtain similar results for the (more general) class of crossing supermodular requirements. Our result extends and improves the (3av+4, 3bv+4, 3)-approximation of Lau et al. Setting ε=0, our result gives the first purely additive guarantee for the unweighted versions of these problems. Our algorithm is based on rounding an LP relaxation for the problem. We also prove that the above cost-degree trade-off (even for the degree-bounded arborescence problem) is optimal relative to the natural LP relaxation. For every 0<ε <1, we show an instance where any arborescence with out-degrees at most bv/1-ε + O(1) has cost at least 1-o(1)/ε times the optimal LP value. For the special case of finding a minimum degree arborescence (without costs), we give a stronger +2 additive approximation. This improves on a result of Lau et al. [13] that gives a 2Δ*+2 guarantee, and Klein et al. [11] that gives a (1+ε)Δ*+O(log1+ε n) bound, where Δ* is the degree of the optimal arborescence. As a corollary of our result, we (almost) settle a conjecture of Bang-Jensen et al. [1] on low-degree arborescences. Our algorithms use the iterative rounding technique of Jain, which was used by Lau et al. and Singh and Lau in the context of degree-bounded network design. It is however non-trivial to extend these techniques to the directed setting without incurring a multiplicative violation in the degree bounds. This is due to the fact that known polyhedral characterization of arborescences has the cut-constraints which, along with degree-constraints, are unsuitable for arguing the existence of integral variables in a basic feasible solution. We overcome this difficulty by enhancing the iterative rounding steps and by means of stronger counting arguments. Our counting technique is quite general, and it also simplifies the proofs of many previous results. We also apply the technique to undirected graphs. We consider the minimum crossing spanning tree problem: given an undirected edge-weighted graph G, edge-subsets Eii=1k, and non-negative integers bii=1k, find a minimum-cost spanning tree (if it exists) in G that contains at most bi edges from each set Ei. We obtain a +(r-1) additive approximation for this problem, when each edge lies in at most r sets; this considerably improves the result of Bilo et al. A special case of this problem is degree-bounded minimum spanning tree, and our result gives a substantially easier proof of the recent +1 approximation of Singh and Lau.

We consider scheduling policies in a client-server system where the server delivers data by broadcasting it to the users. In thesimplest model of the problem, there is a single server that holds n pages of unit size. Multiple requests for these pages arrive over time. At each time slot the server broadcasts exactly one page which satisfies all of the outstanding requests for this page at that time. We consider the problem of minimizing the average response time of requests, where the response time of the request is the duration since the request is placed until the time it is satisfied. For the offline version of this problem we give an algorithm with an approximation ratio of $O(\log^2(n) / \log \log(n))$. More generally, for any $\epsilon>0$, the algorithm achieves an average response time of $(2+\epsilon) \cdot \text{OPT} + O(\log n \cdot \log_{(1+\epsilon)} n)$, which is useful when the optimum value is large. This substantially improves the previously best known approximation factor of $O(\sqrt{n})$ for the problem [N. Bansal, M. Charikar, S. Khanna, and J. Naor, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, British Columbia, ACM, New York, SIAM, Philadelphia, 2005, pp. 215–221]. Our result is based on iteratively relaxing and rounding an auxiliary linear program derived from a natural linear programming relaxation of the problem.

In the weighted paging problem there is a weight (cost) for fetching each page into the cache. We design a randomized O(log k) -competitive online algorithm for the weighted paging problem, where k is the cache size. This is the first randomized o(k)-competitive algorithm and its competitiveness matches the known lower bound on the problem. More generally, we design an O(log(k/(k - h + I)))-competitive online algorithm for the version of the. problem where, the online algorithm has-cache size k and the online algorithm has cache size h les k. Weighted paging is a special case (weighted star metric) of the well known k-server problem for which it is a major open question whether randomization can be useful in obtaining sub-linear competitive algorithms. Therefore, abstracting and extending the insights from paging is a key step in the resolution of the k-server problem. Our solution for the weighted paging problem is based on a two-step approach. In the first step we obtain an O(log k)-competitive fractional algorithm which is based on a novel online primal-dual approach. In the second step we. obtain a randomized algorithm by rounding online the fractional solution to an actual distribution on integral cache, solutions. We conclude with a randomized O(log N)-competitive algorithm for the well studied Metrical Task System problem (MTS) on a metric defined by a weighted star on N leaves, improving upon a previous O(log2N)-competitive algorithm of Blum et al. [9].

We give the first O(l)-speed O(l) approximation polynomial-time algorithms for several nonpreemptive min-sum scheduling problems where jobs arrive over time and must be processed on one machine. More precisely, we give the first O(l)-speed O(l)-approximations for the non-preemptive scheduling problems; l|rj| SigmawjFj(weighted flow time), l |rj| SigmaTj(total tardiness), the broadcast version of 1 |rj| SigmawjFj, an O(I)-speed, 1-approximation for l |rj| Sigma U macrj(throughput maximization), and an O(l)-machine, O(l)-speed O(1)-approximation for l |rj| SigmawjTj(weighted tardiness). Our main contribution is an integer programming formulation whose relaxation is sufficiently close to the integer optimum, and which can be transformed to a schedule on a faster machine.

Speed scaling is a power management technique that involves dynamically changing the speed of a processor. We study policies for setting the speed of the processor for both of the goals of minimizing the energy used and the maximum temperature attained. The theoretical study of speed scaling policies to manage energy was initiated in a seminal paper by Yao et al. [1995], and we adopt their setting. We assume that the power required to run at speed s is P ( s ) = s α for some constant α > 1. We assume a collection of tasks, each with a release time, a deadline, and an arbitrary amount of work that must be done between the release time and the deadline. Yao et al. [1995] gave an offline greedy algorithm YDS to compute the minimum energy schedule. They further proposed two online algorithms Average Rate (AVR) and Optimal Available (OA), and showed that AVR is 2 α − 1 α α -competitive with respect to energy. We provide a tight α α bound on the competitive ratio of OA with respect to energy. We initiate the study of speed scaling to manage temperature. We assume that the environment has a fixed ambient temperature and that the device cools according to Newton's law of cooling. We observe that the maximum temperature can be approximated within a factor of two by the maximum energy used over any interval of length 1/ b , where b is the cooling parameter of the device. We define a speed scaling policy to be cooling-oblivious if it is simultaneously constant-competitive with respect to temperature for all cooling parameters. We then observe that cooling-oblivious algorithms are also constant-competitive with respect to energy, maximum speed and maximum power. We show that YDS is a cooling-oblivious algorithm. In contrast, we show that the online algorithms OA and AVR are not cooling-oblivious. We then propose a new online algorithm that we call BKP. We show that BKP is cooling-oblivious. We further show that BKP is e -competitive with respect to the maximum speed, and that no deterministic online algorithm can have a better competitive ratio. BKP also has a lower competitive ratio for energy than OA for α ≥5. Finally, we show that the optimal temperature schedule can be computed offline in polynomial-time using the Ellipsoid algorithm.

We consider the problem of minimizing the total weighted flow time on a single machine with preemptions. We give an online algorithm that is O ( k )-competitive for k weight classes. This implies an O (log W )-competitive algorithm, where W is the maximum to minimum ratio of weights. This algorithm also implies an O (log n + log P )-approximation ratio for the problem, where P is the ratio of the maximum to minimum job size and n is the number of jobs. We also consider the nonclairvoyant setting where the size of a job is unknown upon its arrival and becomes known to the scheduler only when the job meets its service requirement. We consider the resource augmentation model, and give a (1 + ε)-speed, (1 +1/ε)-competitive online algorithm.

In this paper we introduce a new general framework for set covering problems, based on the combination of randomized rounding of the (near-)optimal solution of the linear programming (LP) relaxation, leading to a partial integer solution, and the application of a well-behaved approximation algorithm to complete this solution. If the value of the solution returned by the latter can be bounded in a suitable way, as is the case for the most relevant generalizations of bin packing, the method leads to improved approximation guarantees, along with a proof of tighter integrality gaps for the LP relaxation. Applying our general framework we obtain a polynomial-time randomized algorithm for d-dimensional vector packing with approximation guarantee arbitrarily close to ln d + 1. For d = 2, this value is 1.693 ..., i.e., we break the natural 2 "barrier" for this case. Moreover, for small values of d this is a notable improvement over the previously-known O(ln d) guarantee by Chekuri and Khanna (2004). For 2-dimensional bin packing with and without rotations, we construct algorithms with performance guarantee arbitrarily close to 1.525..., improving upon previous algorithms with performance guarantee of 2 + epsiv by Jansen and Zhang (2004) for the problem with rotations and1.691... by Caprara (2002) for the problem without rotations. The previously-unknown key property used in our proofs follows from a retrospective analysis of the implications of the landmark bin packing approximation scheme by Fernandez de la Vega and Lueker (1981). We prove that their approximation scheme is "subset oblivious", which leads to numerous applications. Another byproduct of our paper is an algorithm that solves a well-known configuration LP for 2-dimensional bin packing within a factor of (1 + epsiv) for any epsiv gt; 0. Interestingly, we do it without using an approximate separation oracle, which would correspond to a well-known geometric 2-dimensional knapsack. Although separation and optimization are equivalent (M. Grotschel et al, 1988) and the existence of an approximation scheme for the separation problem remains open, we are able to design an approximation scheme for the configuration LP since its objective function is unweighed

We study the Unsplittable Flow Problem (UFP) on line graphs and cycles, focusing on the long-standing open question of whether the problem is APX-hard. We describe a deterministic quasi-polynomial time approximation scheme for UFP on line graphs, thereby ruling out an APX-hardness result, unless NP ⊆ DTIME(2polylog(n)). Our result requires a quasi-polynomial bound on all edge capacities and demands in the input instance. We extend this result to undirected cycle graphs.Earlier results on this problem included a polynomial time (2+ε)-approximation under the assumption that no demand exceeds any edge capacity (the "no-bottleneck assumption") and a super-constant integrality gap if this assumption did not hold. Unlike most earlier work on UFP, our results do not require a no-bottleneck assumption.

We consider the following problem: The Santa Claus has n presents that he wants to distribute among m kids. Each kid has an arbitrary value for each present. Let pij be the value that kid i has for present j. The Santa's goal is to distribute presents in such a way that the least lucky kid is as happy as possible, i.e he tries to maximize mini=1,...,m sumj ∈ Si pij where Si is a set of presents received by the i-th kid.Our main result is an O(log log m/log log log m) approximation algorithm for the restricted assignment case of the problem when pij ∈ pj,0 (i.e. when present j has either value pj or 0 for each kid). Our algorithm is based on rounding a certain natural exponentially large linear programming relaxation usually referred to as the configuration LP. We also show that the configuration LP has an integrality gap of Ω(m1/2) in the general case, when pij can be arbitrary.

The 2-dimensional bin packing problem (2BP) is a generalization of the classical Bin Packing problem and is defined as follows: Given a collection of rectangles specified by their width and height, pack these into the minimum number of square bins of unit size. We study the case of 'orthogonal packing without rotations', where rectangles cannot be rotated and must be packed parallel to the edges of a bin. Often in practical cases of 2BP problems there are additional constraints on how complicated the packing patterns in a bin can be. A well-studied and frequently used constraint is that every rectangle in the packing must be obtainable by recursively applying a sequence of edge-to-edge cuts parallel to the edges of the bin. Such cuts are known as guillotine cuts. Our main result is that the guillotine 2BP problem admits an asymptotic polynomial time approximation scheme. This is in sharp contrast with the fact that the general 2BP problem is APX-Hard. En route to our main result, we show a structural theorem about approximating general guillotine packings by simpler packings, which could be of independent interest.

We first consider online speed scaling algorithms to minimize the energy used subject to the constraint that every job finishes by its deadline. We assume that the power required to run at speed s is P(s) = s/sup /spl alpha//. We provide a tight /spl alpha//sup /spl alpha// bound on the competitive ratio of the previously proposed optimal available algorithm. This improves the best known competitive ratio by a factor of 2/sup /spl alpha//. We then introduce an online algorithm, and show that this algorithm's competitive ratio is at most 2(/spl alpha//(/spl alpha/ - 1))/sup /spl alpha//e/sup /spl alpha//. This competitive ratio is significantly better and is approximately 2e/sup /spl alpha/+1/ for large /spl alpha/. Our result is essentially tight for large /spl alpha/. In particular, as /spl alpha/ approaches infinity, we show that any algorithm must have competitive ratio e/sup /spl alpha// (up to lower order terms). We then turn to the problem of dynamic speed scaling to minimize the maximum temperature that the device ever reaches, again subject to the constraint that all jobs finish by their deadlines. We assume that the device cools according to Fourier's law. We show how to solve this problem in polynomial time, within any error bound, using the ellipsoid algorithm.

Given a metric space G on n nodes, with a start node r and deadlines D(v) for each vertex v, we consider the Deadline-TSP problem of finding a path starting at r that visits as many nodes as possible by their deadlines. We also consider the more general Vehicle Routing with Time-Windows problem, in which each node v also has a release-time R(v) and the goal is to visit as many nodes as possible within their "time-windows" [R(v),D(v)]. No good approximations were known previously for these problems on general metric spaces. We give an O(logn) approximation algorithm for Deadline-TSP, and extend this algorithm to an O(log2n) approximation for the Time-Window problem. We also give a bicriteria approximation algorithm for both problems: Given an ε>0, our algorithm produces a (1/ε) approximation, while exceeding the deadlines by a factor of 1+ε. We use as a subroutine for these results a constant-factor approximation that we develop for a generalization of the orienteering problem in which both the start and the end nodes of the path are fixed. In the process, we give a 3-approximation to the orienteering problem, improving on the previously best known 4-approximation of [6].

Satellite operators have recently begun offering Internet access over their networks. Typically, users connect to the network using a modem for uplink, and a satellite dish for downlink. We investigate how the performance of these networks might be improved by two simple techniques: caching and use of the return path on the modem link. We examine the problem from a theoretical perspective and via simulation. We show that the general problem is NP-hard, as are several special cases, and we give approximation algorithms for them. We then use insights from these cases to design practical heuristic schedulers which leverage caching and the modem downlinks. Via simulation, we show that caching alone can simultaneously reduce bandwidth requirements by 33% and improve response times by 62%. We further show that the proposed schedulers, combined with caching, yield a system that performs far better under high loads than existing systems.

Network throughput and packet delay are two important parameters in the design and the evaluation of routing protocols for ad-hoc networks. While mobility has been shown to increase the capacity of a network, it is not clear whether the delay can be kept low without trading off the throughput. We consider a theoretical framework and propose a routing algorithm which exploits the patterns in the mobility of nodes to provide guarantees on the delay. Moreover, the throughput achieved by the algorithm is only a poly-logarithmic factor off from the optimal. The algorithm itself is fairly simple. In order to analyze its feasibility and the performance guarantee, we used various techniques of probabilistic analysis of algorithms. The approach taken in this paper could be applied to the analyses of some other routing algorithms for mobile ad hoc networks proposed in the literature.

We consider an online version of the oblivious routing problem. Oblivious routing is the problem of picking a routing between each pair of nodes (or a set of flows), without knowledge of the traffic or demand between each pair, with the goal of minimizing the maximum congestion on any edge in the graph. In the online version of the problem, we consider a "repeated game" setting, in which the algorithm is allowed to choose a new routing each night, but is still oblivious to the demands that will occur the next day. The cost of the algorithm at every time step is its competitive ratio, or the ratio of its congestion to the minimum possible congestion for the demands at that time step.We present an algorithm that is (1+ε) competitive with respect to the best algorithm that uses a single routing for the entire sequence of days (known as the optimal static routing). Our result is a strengthening of the recent result of Azar et al [4], who gave a polynomial time algorithm to find an oblivious routing with the best possible competitive ratio, in that our algorithm achieves a competitive ratio arbitrarily to close to that of Azar et al [4], while at the same time performing nearly as well as the optimal static routing for the given sequence of demands. Our work was done independently, but subsequent to that of Azar et al [4].

Often server systems do not implement the best known algorithms for optimizing average Quality of Service (QoS) out of concern of that these algorithms may be insufficiently fair to individual jobs. The standard method for balancing average QoS and fairness is optimize the Lp metric, 1 < p < ∞. Thus we consider server scheduling strategies to optimize the Lp norms of the standard QoS measures, flow and stretch. We first show that there is no no(1)-competitive online algorithm for the Lp norms of either flow or stretch. We then show that the standard clairvoyant algorithms for optimizing average QoS, SJF and SRPT, are O(1+ε)-speed O(1/ε)-competitive for the Lp norms of flow and stretch. And that the standard nonclairvoyant algorithm for optimizing average QoS, SETF, is O(1+ε)-speed O(1/ε(2+2/p))-competitive for the Lp norms of flow. These results argue that these standard algorithms will not starve jobs until the system is near peak capacity. In contrast, we show that the Round Robin, or Processor Sharing algorithm, which is sometimes adopted because of its seeming fairness properties, is not O(1+ε)-speed no(1)-competitive for sufficiently small ε.

Is it possible to reduce the expected response time of every request at a web server, simply by changing the order in which we schedule the requests? That is the question we ask in this paper.This paper proposes a method for improving the performance of web servers servicing static HTTP requests. The idea is to give preference to requests for small files or requests with short remaining file size, in accordance with the SRPT (Shortest Remaining Processing Time) scheduling policy.The implementation is at the kernel level and involves controlling the order in which socket buffers are drained into the network. Experiments are executed both in a LAN and a WAN environment. We use the Linux operating system and the Apache and Flash web servers.Results indicate that SRPT-based scheduling of connections yields significant reductions in delay at the web server. These result in a substantial reduction in mean response time and mean slowdown for both the LAN and WAN environments. Significantly, and counter to intuition, the requests for large files are only negligibly penalized or not at all penalized as a result of SRPT-based scheduling.

We consider the following clustering problem: we have a complete graph on n vertices (items), where each edge (u, /spl upsi/) is labeled either + or - depending on whether a and /spl upsi/ have been deemed to be similar or different. The goal is to produce a partition of the vertices (a clustering) that agrees as much as possible with the edge labels. That is, we want a clustering that maximizes the number of + edges within clusters, plus the number of - edges between clusters (equivalently, minimizes the number of disagreements: the number of - edges inside clusters plus the number of + edges between clusters). This formulation is motivated from a document clustering problem in which one has a pairwise similarity function f learned from past data, and the goal is to partition the current set of documents in a way that correlates with f as much as possible; it can also be viewed as a kind of "agnostic learning" problem. An interesting feature of this clustering formulation is that one does not need to specify the number of clusters k as a separate parameter, as in measures such as k-median or min-sum or min-max clustering. Instead, in our formulation, the optimal number of clusters could be any value between 1 and n, depending on the edge labels. We look at approximation algorithms for both minimizing disagreements and for maximizing agreements. For minimizing disagreements, we give a constant factor approximation. For maximizing agreements we give a PTAS. We also show how to extend some of these results to graphs with edge labels in [-1, +1], and give some results for the case of random noise.