The goal in the stochastic vertex cover problem is to obtain an approximately minimum vertex cover for a graph G⋆ that is realized by sampling each edge independently with some probability p∈ (0, 1] in a base graph G = (V, E). The algorithm is given the base graph G and the probability p as inputs, but its only access to the realized graph G⋆ is through queries on individual edges in G that reveal the existence (or not) of the queried edge in G⋆. In this paper, we resolve the central open question for this problem: to find a (1+ε)-approximate vertex cover using only Oε(n/p) edge queries. Prior to our work, there were two incomparable state-of-the-art results for this problem: a (3/2+ε)-approximation using Oε(n/p) queries (Derakhshan, Durvasula, and Haghtalab, 2023) and a (1+ε)-approximation using Oε((n/p)· RS(n)) queries (Derakhshan, Saneian, and Xun, 2025), where RS(n) is known to be at least 2Ω(logn/loglogn) and could be as large as n/2Θ(log* n). Our improved upper bound of Oε(n/p) matches the known lower bound of Ω(n/p) for any constant-factor approximation algorithm for this problem (Behnezhad, Blum, and Derakhshan, 2022). A key tool in our result is a new concentration bound for the size of minimum vertex cover on random graphs, which might be of independent interest.

For any є ∈ (0,1), we give a randomized algorithm which given n points in (d, ℓp) for p ∈ [1,2], constructs a directed graph using O(n2 − Ω(є)) edges in nearly-matching time, such that shortest path lengths approximate ℓp-distances up to a (1 + є)-factor. The graph uses non-metric Steiner nodes (known to be necessary) and improves upon the prior construction of Andoni and Zhang using O(n2−Ω(є2)) edges. We show that our construction is nearly-optimal by showing there exists a set of points in d where any (1+є)-approximate directed Steiner spanner must use Ω(n2 − O(є)) edges.

Increasing demand from AI/ML workloads is exacerbating the rising energy consumption of data centers. Recent advances in hardware such as NVIDIA's Multi Instance GPUs (MIGs) offer improvements in flexibility and computational power and the opportunity for data centers to manage incoming jobs in energy-efficient ways, while maintaining acceptable performance. The challenge in achieving this multi-objective in a MIG environment through job scheduling is multi-faceted. Firstly, for a given MIG configuration, one seeks an easy-toimplement scheduling algorithm which selects a job from the queue as well as decides on which slice in the configuration the job runs. Secondly, for the identified scheduling algorithm, a particular MIG configuration may not always be suitable (as the workload fluctuates) and may need to be repartitioned. We tackle both problems using simulations and reinforcement learning (RL). We present a dynamic repartitioning scheduling framework for a single MIG as a solution to a multi-objective heterogeneous machine scheduling problem with preemption. In particular, we compare four scheduling algorithms and identify a promising one. Then, we employ reinforcement learning to perform dynamic repartitioning over a day. Furthermore, using a diurnal workload pattern based on real-world data center traces, we demonstrate the superiority of our dynamic repartitioning algorithm over twice-daily repartitioning (26%), static partitioning (31%) and no partitioning at all (68%) according to a multi-objective function of energy consumption and tardiness. Our results indicate specific preferred configurations at different times of the day under different queue conditions, suggesting a policy for predictive and automatic reconfiguration.

We use contention resolution schemes (CRS) to derive algorithms for the fair rationing of a single resource when agents have stochastic demands. We aim to provide ex-ante guarantees on the level of service provided to each agent, who may measure service in different ways (Type-I, II, or III), calling for CRS under different feasibility constraints (rank-1 matroid or knapsack). We are particularly interested in two-order CRS where the agents are equally likely to arrive in a known forward order or its reverse, which is motivated by online rationing at food banks. Indeed, for a mobile pantry driving along cities to ration food, it is equally efficient to drive that route in reverse on half of the days, and we show that doing so significantly improves the service guarantees that are possible, being more "fair" to the cities at the back of the route.

High-Bandwidth Memory (HBM) is a decade-old memory technology that is increasingly commonly being used in highly-parallel machines such as GPUs and multicores. Comparatively, HBM has higher bandwidth, smaller capacity, and similar latency to other DRAM technologies. Many systems use both HBM and other DRAM technologies, where HBM is naturally closer to the processor in the conceptual memory hierarchy. Thus, a natural resulting question is how one should best manage a collection of processes running on a HBM/DRAM memory hierarchy. Prior work introduced a theoretical model for addressing this question, and gave a competitive policy for the objective of minimizing makespan. Our main technical contribution is to give a competitive policy for the more commonly appropriate total/average response/completion time objective. However, we believe the broader, and more important contribution, is to make explicit the case (hinted at in the prior literature) that managing an HBM/DRAM hierarchy should be thought of as a parallel scheduling problem. To that end, we introduce a new online scheduling model that we call the semi-normal model. We then show how to use a competitive algorithm for scheduling in the semi-normal model as a black box to obtain a competitive algorithm for managing a HBM/DRAM memory hierarchy. Thus, as a result of this black-box conversion, competitiveness results in the semi-normal model translate (essentially) automatically into competitiveness results in the HBM/DRAM management model. Our main technical result is then an application of such a translation. That is, we show that a natural variant of the Round Robin (processor sharing) algorithm, naturally adapted for the seminormal model, is competitive for the objective of average/total completion time. Thus, we obtain an algorithm for managing a HBM/DRAM hierarchy that is competitive for the objective of average/total completion time, using this black-box reduction.

This paper addresses point-to-point packet routing in undirected networks, which is the most important communication primitive in most networks. The main result proves the existence of routing tables that deterministically guarantee a polylog-competitive completion-time:

An important goal of modern scheduling systems is to efficiently manage power usage. In energy-efficient scheduling, the operating system controls the speed at which a machine is processing jobs with the dual objective of minimizing energy consumption and optimizing the quality of service cost of the resulting schedule. Since machine-learned predictions about future requests can often be learned from historical data, a recent line of work on learning-augmented algorithms aims to achieve improved performance guarantees by leveraging predictions. In particular, for energy-efficient scheduling, Bamas et. al. [NeurIPS '20] and Antoniadis et. al. [SWAT '22] designed algorithms with predictions for the energy minimization with deadlines problem and achieved an improved competitive ratio when the prediction error is small while also maintaining worst-case bounds even when the prediction error is arbitrarily large. In this paper, we consider a general setting for energy-efficient scheduling and provide a flexible learning-augmented algorithmic framework that takes as input an offline and an online algorithm for the desired energy-efficient scheduling problem. We show that, when the prediction error is small, this framework gives improved competitive ratios for many different energy-efficient scheduling problems, including energy minimization with deadlines, while also maintaining a bounded competitive ratio regardless of the prediction error. Finally, we empirically demonstrate that this framework achieves an improved performance on real and synthetic datasets.

Longest Increasing Subsequence (LIS) is a fundamental statistic of a sequence, and has been studied for decades. While the LIS of a sequence of length n can be computed exactly in time $O(n\log n)$, the complexity of estimating the (length of the) LIS in sublinear time, especially when LIS $\ll n$, is still open. We show that for any $n\in\mathbb{N}$ and $\lambda=o(1)$, there exists a (randomized) non-adaptive algorithm that, given a sequence of length n with LIS $\geq\lambda n$, approximates the LIS up to a factor of $1/\lambda^{o(1)}$ in $ n^{o(1)}/\lambda$ time. Our algorithm improves upon prior work substantially in terms of both approximation and run-time: (i) we provide the first sub-polynomial approximation for LIS in sub-linear time; and (ii) our run-time complexity essentially matches the trivial sample complexity lower bound of $\Omega(1/\lambda)$, which is required to obtain any non-trivial approximation of the LIS. As part of our solution, we develop two novel ideas which may be of independent interest. First, we define a new Genuine-LIS problem, in which each sequence element may be either genuine or corrupted. In this model, the user receives unrestricted access to the actual sequence, but does not know a priori which elements are genuine. The goal is to estimate the LIS using genuine elements only, with the minimal number of tests for genuineness. The second idea, Precision Tree, enables accurate estimations for composition of general functions from “coarse” (sub-)estimates. Precision Tree essentially generalizes classical precision sampling, which works only for summations. As a central tool, the Precision Tree is pre-processed on a set of samples, which thereafter is repeatedly used by multiple components of the algorithm, improving their amortized complexity.

First introduced in 1954, linear probing is one of the oldest data structures in computer science, and due to its unrivaled data locality, it continues to be one of the fastest hash tables in practice. It is widely believed and taught, however, that linear probing should never be used at high load factors; this is because primary-clustering effects cause insertions at load factor $1 - 1 /x$ to take expected time $Θ(x^2)$ (rather than the ideal $Θ(x)$). The dangers of primary clustering, first discovered by Knuth in 1963, have been taught to generations of computer scientists, and have influenced the design of some of many widely used hash tables. We show that primary clustering is not a foregone conclusion. We demonstrate that small design decisions in how deletions are implemented have dramatic effects on the asymptotic performance of insertions, so that, even if a hash table operates continuously at a load factor $1 - Θ(1/x)$, the expected amortized cost per operation is $\tilde{O}(x)$. This is because tombstones created by deletions actually cause an anti-clustering effect that combats primary clustering. We also present a new variant of linear probing (which we call graveyard hashing) that completely eliminates primary clustering on \emph{any} sequence of operations: if, when an operation is performed, the current load factor is $1 - 1/x$ for some $x$, then the expected cost of the operation is $O(x)$. One corollary is that, in the external-memory model with a data blocks of size $B$, graveyard hashing offers the following remarkable guarantee: at any load factor $1 - 1/x$ satisfying $x = o(B)$, graveyard hashing achieves $1 + o(1)$ expected block transfers per operation. Past external-memory hash tables have only been able to offer a $1 + o(1)$ guarantee when the block size $B$ is at least $Ω(x^2)$.

We present a (1+ε)-approximate parallel algorithm for computing shortest paths in undirected graphs, achieving poly(logn) depth and m poly(logn) work for n-nodes m-edges graphs. Although sequential algorithms with (nearly) optimal running time have been known for several decades, near-optimal parallel algorithms have turned out to be a much tougher challenge. For (1+ε)-approximation, all prior algorithms with poly(logn) depth perform at least Ω(mn c ) work for some constant c>0. Improving this long-standing upper bound obtained by Cohen (STOC’94) has been open for 25 years.

We consider virtual circuit routing protocols with an objective of minimizing energy in a network of components that are speed scalable, and that may be shut down when idle. We assume the standard model for component power: the power consumed by a component with load (speed) $s$ is $\sigma+ s^\alpha$, where $\sigma$ is the static power and the exponent $\alpha>1$. We obtain a very simple $O(\log^\alpha k)$-approximation algorithm for multicommodity routing, where $k$ is the number of demand pairs. This improves upon previous results by several logarithmic factors. The key step in our algorithm is a random sampling technique that we call hallucination, which is reminiscent of the sample-augment framework for buy-at-bulk problems, and sampling in cut-sparsification algorithms. We also consider the online setting of the problem, where demand pairs arrive over time. We show that our offline algorithm naturally extends to the online setting, and obtain a randomized competitive ratio of $\tilde{O}( \log^{3\alpha + 1} k)$, which is the first nontrivial bound. The analysis of this algorithm involves the study of priority multicommodity flows, where edges and demand-pairs have priorities and each demand-pair must route its flow only on edges of lower priority. We establish a polylogarithmic flow-cut gap for these priority flows, which we believe is of independent interest. Finally, we show how our technique can be used to achieve a randomized $( O(\log m), O(\log^2 m))$ bicriteria competitive algorithm for the uniform capacitated network design problem, where $m$ is the number of edges. Here, every edge has a cost $c_e$ and uniform capacity $q$, and the goal is to choose the minimum cost subgraph that can support the given multicommodity demand. This is the first online algorithm for this problem. In fact, our approach also improves prior results in the offline setting by several logarithmic factors.

Often in a scheduling problem, there is uncertainty about the jobs to be processed. The issue of uncertainty regarding the machines has been much less studied. In this article, we study a scheduling environment in which jobs first need to be grouped into some sets before the number of machines is known, and then the sets need to be scheduled on machines without being separated. To evaluate algorithms in such an environment, we introduce the idea of an α-robust algorithm, one that is guaranteed to return a schedule on any number m of machines that is within an α factor of the optimal schedule on m machine, where the optimum is not subject to the restriction that the sets cannot be separated. Under such environment, we give a (5\3+ϵ)-robust algorithm for scheduling on parallel machines to minimize makespan and show a lower bound 4\3. For the special case when the jobs are infinitesimal, we give a 1.233-robust algorithm with an asymptotic lower bound of 1.207. We also study a case of fair allocation, where the objective is to minimize the difference between the maximum and minimum machine load.

We present the first algorithm for maintaining a maximal independent set (MIS) of a fully dynamic graph-which undergoes both edge insertions and deletions-in polylogarithmic time. Our algorithm is randomized and, per update, takes O(log2Δ log2n) expected time. Furthermore, the algorithm can be adjusted to have O(log2Δ log4n) worst-case update-time with high probability. Here, n denotes the number of vertices and Δ is the maximum degree in the graph. The MIS problem in fully dynamic graphs has attracted significant attention after a breakthrough result of Assadi, Onak, Schieber, and Solomon [STOC'18] who presented an algorithm with O(m3/4) update-time (and thus broke the natural Ω(m) barrier) where m denotes the number of edges in the graph. This result was improved in a series of subsequent papers, though, the update-time remained polynomial. In particular, the fastest algorithm prior to our work had Õ(min{√n, m1/3}) update-time [Assadi et al. SODA'19]. Our algorithm maintains the lexicographically first MIS over a random order of the vertices. As a result, the same algorithm also maintains a 3-approximation of correlation clustering. We also show that a simpler variant of our algorithm can be used to maintain a random-order lexicographically first maximal matching in the same update-time.

Many modern parallel systems, such as MapReduce, Hadoop and Spark, can be modeled well by the MPC model. The MPC model captures well coarse-grained computation on large data --- data is distributed to processors, each of which has a sublinear (in the input data) amount of memory and we alternate between rounds of computation and rounds of communication, where each machine can communicate an amount of data as large as the size of its memory. This model is stronger than the classical PRAM model, and it is an intriguing question to design algorithms whose running time is smaller than in the PRAM model. In this paper, we study two fundamental problems, $2$-edge connectivity and $2$-vertex connectivity (biconnectivity). PRAM algorithms which run in $O(\log n)$ time have been known for many years. We give algorithms using roughly log diameter rounds in the MPC model. Our main results are, for an $n$-vertex, $m$-edge graph of diameter $D$ and bi-diameter $D'$, 1) a $O(\log D\log\log_{m/n} n)$ parallel time $2$-edge connectivity algorithm, 2) a $O(\log D\log^2\log_{m/n}n+\log D'\log\log_{m/n}n)$ parallel time biconnectivity algorithm, where the bi-diameter $D'$ is the largest cycle length over all the vertex pairs in the same biconnected component. Our results are fully scalable, meaning that the memory per processor can be $O(n^δ)$ for arbitrary constant $δ>0$, and the total memory used is linear in the problem size. Our $2$-edge connectivity algorithm achieves the same parallel time as the connectivity algorithm of Andoni et al. (FOCS 2018). We also show an $Ω(\log D')$ conditional lower bound for the biconnectivity problem.

There is a rapidly growing need for scalable algorithms that solve classical graph problems, such as maximum matching and minimum vertex cover, on massive graphs. For massive inputs, several different computational models have been introduced, including the streaming model, the distributed communication model, and the massively parallel computation (MPC) model that is a common abstraction of MapReduce-style computation. In each model, algorithms are analyzed in terms of resources such as space used or rounds of communication needed, in addition to the more traditional approximation ratio. In this paper, we give a single unified approach that yields better approximation algorithms for matching and vertex cover in all these models. The highlights include: The first one pass, significantly-better-than-2-approximation for matching in random arrival streams that uses subquadratic space, namely a (1.5 + ε)-approximation streaming algorithm that uses Õ(n15) space for constant ε > 0. The first 2-round, better-than-2-approximation for matching in the MPC model that uses subquadratic space per machine, namely a (1.5 + ε)-approximation algorithm with memory per machine for constant ε > 0. By building on our unified approach, we further develop parallel algorithms in the MPC model that give a (1+∊)-approximation to matching and an O(1)-approximation to vertex cover in only O(log log n) MPC rounds and O(n/polylog(n)) memory per machine. These results settle multiple open questions posed by Czumaj et al. [STOC 2018]. We obtain our results by a novel combination of two previously disjoint set of techniques, namely randomized composable coresets and edge degree constrained subgraphs (EDCS). We significantly extend the power of these techniques and prove several new structural results. For example, we show that an EDCS is a sparse certificate for large matchings and small vertex covers that is quite robust to sampling and composition.

Many modern parallel systems, such as MapReduce, Hadoop and Spark, can be modeled well by the MPC model. The MPC model captures well coarse-grained computation on large data — data is distributed to processors, each of which has a sublinear (in the input data) amount of memory and we alternate between rounds of computation and rounds of communication, where each machine can communicate an amount of data as large as the size of its memory. This model is stronger than the classical PRAM model, and it is an intriguing question to design algorithms whose running time is smaller than in the PRAM model. One fundamental graph problem is connectivity. On an undirected graph with n nodes and m edges, O(log n) round connectivity algorithms have been known for over 35 years. However, no algorithms with better complexity bounds were known. In this work, we give fully scalable, faster algorithms for the connectivity problem, by parameterizing the time complexity as a function of the diameter of the graph. Our main result is a O(log D log log_m/n n) time connectivity algorithm for diameter-d graphs, using Θ(m) total memory. If our algorithm can use more memory, it can terminate in fewer rounds, and there is no lower bound on the memory per processor. We extend our results to related graph problems such as spanning forest, finding a DFS sequence, exact/approximate minimum spanning forest, and bottleneck spanning forest. We also show that achieving similar bounds for reachability in directed graphs would imply faster boolean matrix multiplication algorithms. We introduce several new algorithmic ideas. We describe a general technique called double exponential speed problem size reduction which roughly means that if we can use total memory n to reduce a problem from size n to n/k, for k=(N/n)^Θ(1) in one phase, then we can solve the problem in O(loglog_N/n n) phases. In order to achieve this fast reduction for graph connectivity, we use a multistep algorithm. One key step is a carefully constructed truncated broadcasting scheme where each node broadcasts neighbor sets to its neighbors in a way that limits the size of the resulting neighbor sets. Another key step is random leader contraction, where we choose a smaller set of leaders than many previous works do.

We present a simple randomized reduction from fully-dynamic integral matching algorithms to fully-dynamic "approximately-maximal" fractional matching algorithms. Applying this reduction to the recent fractional matching algorithm of Bhattacharya, Henzinger, and Nanongkai (SODA 2017), we obtain a novel result for the integral problem. Specifically, our main result is a randomized fully-dynamic $(2+ε)$-approximate integral matching algorithm with small polylog worst-case update time. For the $(2+ε)$-approximation regime only a \emph{fractional} fully-dynamic $(2+ε)$-matching algorithm with worst-case polylog update time was previously known, due to Bhattacharya et al.~(SODA 2017). Our algorithm is the first algorithm that maintains approximate matchings with worst-case update time better than polynomial, for any constant approximation ratio. As a consequence, we also obtain the first constant-approximate worst-case polylogarithmic update time maximum weight matching algorithm.

Finding a maximum matching is a fundamental algorithmic problem and is fairly well understood in traditional sequential computing models. Some modern applications require that we handle massive graphs and hence we need to consider algorithms in models that do not allow the entire input graph to be held in the memory of one computer, or models in which the graph is evolving over time. We introduce a new concept called an "Edge Degree Constrained Subgraph (EDCS)", which is a subgraph that is guaranteed to contain a large matching, and which can be identified via local conditions. We then show how to use an EDCS to find 1.5-approximate matchings in several different models including Map Reduce, streaming and distributed computing. We can also use an EDCS to maintain a 1.5-optimal matching in a dynamic graph. This work is joint with Sepehr Asadi, Aaron Bernstein, Mohammad Hossein Bateni and Vahab Marrokni.

Often in a scheduling problem, there is uncertainty about the jobs to be processed. The issue of uncertainty regarding the machines has been much less studied. In this paper, we study a scheduling environment in which jobs first need to be grouped into some sets before the number of machines is known, and then the sets need to be scheduled on machines without being separated. In order to evaluate algorithms in such an environment, we introduce the idea of an α-robust algorithm, one which is guaranteed to return a schedule on any number m of machines that is within an α factor of the optimal schedule on m machine, where the optimum is not subject to the restriction that the sets cannot be separated. Under such environment, we give a -robust algorithm for scheduling on parallel machines to minimize makespan, and show a lower bound . For the special case when the jobs are infinitesimal, we give a 1.233-robust algorithm with an asymptotic lower bound of 1.207. We also study a case of fair allocation, where the objective is to minimize the difference between the maximum and minimum machine load.

The knapsack problem is a fundamental problem in combinatorial optimization. It has been studied extensively from theoretical as well as practical perspectives as it is one of the most well-known NP-hard problems. The goal is to pack a knapsack of size t with the maximum value from a collection of n items with given sizes and values.

We consider a setting where selfish agents want to schedule jobs on related machines. The agent submitting a job picks a server that minimizes a linear combination of the server price and the resulting response time for that job on the selected server. The manager's task is to maintain server prices to (approximately) optimize the maximum response time, which is a measure of social good. We show that the existence of a pricing scheme with certain competitiveness is equivalent to the existence of a monotone immediate-dispatch algorithm. Our main result is a monotone immediate-dispatch algorithm that is O(1)-competitive with respect to the maximum response time.

This paper investigates the task of load balancing where the objective function is to minimize the p-norm of loads, for p\geq 1, in both static and incremental settings. We consider two closely related load balancing problems. In the bipartite matching problem we are given a bipartite graph G=(C\cup S, E) and the goal is to assign each client c\in C to a server s\in S so that the p-norm of assignment loads on S is minimized. In the graph orientation problem the goal is to orient (direct) the edges of a given undirected graph while minimizing the p-norm of the out-degrees. The graph orientation problem is a special case of the bipartite matching problem, but less complex, which leads to simpler algorithms. For the graph orientation problem we show that the celebrated Chiba-Nishizeki peeling algorithm provides a simple linear time load balancing scheme whose output is an orientation that is 2-competitive, in a p-norm sense, for all p\geq 1. For the bipartite matching problem we first provide an offline algorithm that computes an optimal assignment. We then extend this solution to the online bipartite matching problem with reassignments, where vertices from C arrive in an online fashion together with their corresponding edges, and we are allowed to reassign an amortized O(1) vertices from C each time a new vertex arrives. In this online scenario we show how to maintain a single assignment that is 8-competitive, in a p-norm sense, for all p\geq 1.

This paper considers the online machine minimization problem, a basic real time scheduling problem. The setting for this problem consists of n jobs that arrive over time, where each job has a deadline by which it must be completed. The goal is to design an online scheduler that feasibly schedules the jobs on a nearly minimal number of machines. An algorithm is c-machine optimal if the algorithm will feasibly schedule a collection of jobs on c ·m machines if there exists a feasible schedule on m machines. For over two decades the best known result was a O(log P)-machine optimal algorithm, where P is the ratio of the maximum to minimum job size. In a recent breakthrough, a O(log m)-machine optimal algorithm was given. In this paper, we exponentially improve on this recent result by giving a O(log log m)-machine optimal algorithm.

For all practical purposes, the Micali-Vazirani general graph maximum matching algorithm is still the most efficient known algorithm for the problem. The purpose of this paper is to provide a complete proof of correctness of the algorithm in the simplest possible terms; graph-theoretic machinery developed for this purpose also helps simplify the algorithm.

Over the past two decades, fair resource allocation problems have received considerable attention in a variety of application areas. However, little progress has been made in the design of distributed algorithms with convergence guarantees for general and commonly used $α$-fair allocations. In this paper, we study weighted $α$-fair packing problems, that is, the problems of maximizing the objective functions (i) $\sum_j w_j x_j^{1-α}/(1-α)$ when $α> 0$, $α\neq 1$ and (ii) $\sum_j w_j \ln x_j$ when $α= 1$, over linear constraints $Ax \leq b$, $x\geq 0$, where $w_j$ are positive weights and $A$ and $b$ are non-negative. We consider the distributed computation model that was used for packing linear programs and network utility maximization problems. Under this model, we provide a distributed algorithm for general $α$ that converges to an $\varepsilon-$approximate solution in time (number of distributed iterations) that has an inverse polynomial dependence on the approximation parameter $\varepsilon$ and poly-logarithmic dependence on the problem size. This is the first distributed algorithm for weighted $α-$fair packing with poly-logarithmic convergence in the input size. The algorithm uses simple local update rules and is stateless (namely, it allows asynchronous updates, is self-stabilizing, and allows incremental and local adjustments). We also obtain a number of structural results that characterize $α-$fair allocations as the value of $α$ is varied. These results deepen our understanding of fairness guarantees in $α-$fair packing allocations, and also provide insight into the behavior of $α-$fair allocations in the asymptotic cases $α\rightarrow 0$, $α\rightarrow 1$, and $α\rightarrow \infty$.

Maximum cardinality matching is a fundamental algorithmic problem with many algorithms and applications. The fully dynamic version, in which edges are inserted and deleted over time has also been the subject of much attention. Existing algorithms for dynamic matching (in general n-vertex m-edge graphs) fall into two groups: there are fast (mostly randomized) algorithms that achieve a 2-approximation or worse, and there are slow algorithms with update time that achieve a better-than-2 approximation. Thus the obvious question is whether we can design an algorithm that achieves a tradeoff between these two: a update time and a better-than-2 approximation simultaneously. We answer this question in the affirmative. Previously, such bounds were only known for the special case of bipartite graphs. Our main result is a fully dynamic deterministic algorithm that maintains a (3/2 + ∊)-approximation in amortized update time O(m1/4∊–2.5). In addition to achieving the trade-off described above, our algorithm manages to be polynomially faster than all existing deterministic algorithms (excluding an existing log n-approximation of Onak and Rubinfeld), while still maintaining a better-than-2 approximation. We also give stronger results for graphs whose arboricity is at most α. We show how to maintain a (1 + ∊)-approximate fractional matching or a (3/2 + ∊)-approximate integral matching in worst-case time O(α(α + log n)) for constant ∊. When the arboricity is constant, this bound is O(log n) and when the arboricity is polylogarithmic the update time is also polylogarithmic. Previous results for small arboricity non-bipartite graphs could only maintain a maximal matching (2-approximation). We maintain the approximate matching without explicitly using augmenting paths. We define an intermediate graph, called an EDCS and show that the EDCS H contains a large matching, and show how to maintain an EDCS in G. The EDCS was used in previous works on bipartite graphs, however the details and proofs are completely different in general graphs. The algorithm for bipartite graphs relies on ideas from flows and cuts to non-constructively prove the existence of a good matching in H, but these ideas do not seem to extend to non-bipartite graphs. In this paper we instead explicitly construct a large fractional matching in H. In some cases we can guarantee that this fractional matching is γ-restricted, which means that it only uses values either in the range [0, γ] or 1. We then combine this matching with a new structural property of maximum matchings in non-bipartite graphs, which is analogous to the cut induced by maximum matchings in bipartite graphs.

Recently, a new convex formulation of IBM Model 2 was introduced. In this paper we develop the theory further and introduce a class of convex relaxations for latent variable models which include IBM Model 2. When applied to IBM Model 2, our relaxation class subsumes the previous relaxation as a special case. As proof of concept, we study a new relaxation of IBM Model 2 which is simpler than the previous algorithm: the new relaxation relies on the use of nothing more than a multinomial EM algorithm, does not require the tuning of a learning rate, and has some favorable comparisons to IBM Model 2 in terms of F-Measure. The ideas presented could be applied to a wide range of NLP and machine learning problems.

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.

IBM Model 1 is a classical alignment model.Of the first generation word-based SMT models, it was the only such model with a concave objective function.For concave optimization problems like IBM Model 1, we have guarantees on the convergence of optimization algorithms such as Expectation Maximization (EM).However, as was pointed out recently, the objective of IBM Model 1 is not strictly concave and there is quite a bit of alignment quality variance within the optimal solution set.In this work we detail a strictly concave version of IBM Model 1 whose EM algorithm is a simple modification of the original EM algorithm of Model 1 and does not require the tuning of a learning rate or the insertion of an l 2 penalty.Moreover, by addressing Model 1's shortcomings, we achieve AER and F-Measure improvements over the classical Model 1 by over 30%.

Communications in datacenter jobs (such as the shuffle operations in MapReduce applications) often involve many parallel flows, which may be processed simultaneously. This highly parallel structure presents new scheduling challenges in optimizing job-level performance objectives in data centers. Chowdhury and Stoica introduced the coflow abstraction to capture these communication patterns, and recently Chowdhury et al. developed effective heuristics to schedule coflows. In this paper, we consider the problem of efficiently scheduling coflows with release dates so as to minimize the total weighted completion time, which has been shown to be strongly NP-hard. Our main result is the first polynomial-time deterministic approximation algorithm for this problem, with an approximation ratio of 67/3, and a randomized version of the algorithm, with a ratio of 9+16√2/3. Our results use techniques from both combinatorial scheduling and matching theory, and rely on a clever grouping of coflows. We also run experiments on a Facebook trace to test the practical performance of several algorithms, including our deterministic algorithm. Our experiments suggest that simple algorithms provide effective approximations of the optimal, and that our deterministic algorithm has near-optimal performance.

Using a recent convex formulation of IBM Model 2, we propose a new initialization scheme which has some favorable comparisons to the standard method of initializing IBM Model 2 with IBM Model 1.Additionally, we derive the Viterbi alignment for the convex relaxation of IBM Model 2 and show that it leads to better F-Measure scores than those of IBM Model 2.

This paper considers max-min fair rate allocation and routing in energy harvesting networks where fairness is required among both the nodes and the time slots. Unlike most previous work on fairness, we focus on multihop topologies and consider different routing methods. We assume a predictable energy profile and focus on the design of efficient and optimal algorithms that can serve as benchmarks for distributed and approximate algorithms. We first develop an algorithm that obtains a max-min fair rate assignment for any given (time-variable or time-invariable) unsplittable routing or a routing tree. For time-invariable unsplittable routing, we also develop an algorithm that finds routes that maximize the minimum rate assigned to any node in any slot. For fractional routing, we study the joint routing and rate assignment problem. We develop an algorithm for the time-invariable case with constant rates. We show that the time-variable case is at least as hard as the 2-commodity feasible flow problem and design an FPTAS to combat the high running time. Finally, we show that finding a max-min fair unsplittable routing or a routing tree is NP-hard, even for a time horizon of a single slot. Our analysis provides insights into the problem structure and can be applied to other related fairness problems.

We consider virtual circuit routing protocols, with an objective of minimizing energy, in a network of components that are speed scalable, and that may be shutdown when idle. We assume that the speed s of a link is proportional to its load, and assume the standard model for component power, namely that the power is some constant static power σ plus sα, where typically α ∊ [1.1,3]. We give a polynomial-time offline algorithm for multicommodity routing, that has approximation ratio O(loga k), where k is the number of demand pairs. This is obtained as a combination of three natural combinatorial algorithms. The key step of the algorithm design is a random sampling technique that we call hallucination, which is reminiscent of the Sample-Augment framework for solving Buy-at-Bulk type problems, and sampling in cut-sparsification algorithms. The analysis of the approximation ratio is then a direct consequence of the flow-cut gap for multicommodity flow. The algorithm extends rather naturally to an online algorithm, which we show has competitive ratio Õ(log3a+1 k). The analysis of the online algorithm introduces a natural “priority” multicommodity flow problem, and bounds the priority multicommodity flow-cut gap-this might also be of independent interest. We also explain how our hallucination technique can be used to achieve an (O(log km), O(logkm)) bicriteria approximation result for the problem of buying a minimum cost collection of unit-capacitated edges to support a concurrent multicommodity flow, where m is the number of links in the network.

Consider the following edge-orientation problem: edges of a graph appear online one-by-one and they to be directed—given an “orientation”. We want to ensure that the in-degree of each vertex remains low. (This is a simple case of scheduling unit-sized jobs on machines, where each job can only go on one of two machines.) If the edge-orientations we assign are irrevocable, we suffer a significant loss in quality due to online decision-making (as compared to the offline performance). For instance the best online competitive ratio achievable is Θ(log m) for even this toy problem. But what if the decisions are not irrevocable — what if we allow a limited number of reassignments? Can we do much better? We show that indeed we can. For instance, for edge-orientation, we can achieve a constant-competitive load while doing only a constant number of re-orientations per edge (in an amortized sense). For more substantial problems, our results are as follows: For online matching, where the left vertices arrive online and must be matched to the right vertices, we give an algorithm that reassigns the left vertices an (amortized) constant number of times, and maintains a constant factor to the optimal load on the right vertices. We extend this to restricted machine scheduling with arbitrary sized jobs and give an algorithm that maintains load which is O(log log mn) times the optimum, and reassigns each job only an (amortized) constant number of times. Consider a digraph with a single source, where sinks arrive online and want to send unit flow to the source. The goal is to minimize the congestion on the edges. Suppose there is an offline flow such that the total length of the flow paths is F*. We give an algorithm that reroutes flow along O(F*) edges and achieves a O(1)-approximation to the congestion.

We consider circuit routing with an objective of minimizing energy, in a network of routers that are speed scalable and that may be shutdown when idle. It is known that this energy minimization problem can be reduced to a capacitated flow network design problem, where vertices have a common capacity but arbitrary costs, and the goal is to choose a minimum cost collection of vertices whose induced subgraph will support the specified flow requirements. For the multicast (single-sink) capacitated design problem we give a polynomial-time algorithm that is O(log3 n)- approximate with O(log4 n) congestion. This translates back to a O(log4α+3 n)-approximation for the multicast energy-minimization routing problem, where α is the polynomial exponent in the dynamic power used by a router. For the unicast (multicommodity) capacitated design problem we give a polynomial-time algorithm that is O(log5 n)-approximate with O(log12 n) congestion, which translates back to a O(log12α+5 n)-approximation for the unicast energy-minimization routing problem.

The IBM translation models have been hugely influential in statistical machine translation; they are the basis of the alignment models used in modern translation systems.Excluding IBM Model 1, the IBM translation models, and practically all variants proposed in the literature, have relied on the optimization of likelihood functions or similar functions that are non-convex, and hence have multiple local optima.In this paper we introduce a convex relaxation of IBM Model 2, and describe an optimization algorithm for the relaxation based on a subgradient method combined with exponentiated-gradient updates.Our approach gives the same level of alignment accuracy as IBM Model 2.

This article concerns an online packet scheduling problem that arises as a natural model for buffer management at a network router. Packets arrive at a router at integer time steps, and are buffered upon arrival. Packets have non-negative weights and integer deadlines that are (weakly) increasing in their arrival times. In each integer time step, at most one packet can be sent. The objective is to maximize the sum of the weights of the packets that are sent by their deadlines. The main results include an optimal (ϕ := (1 + √ 5)/2 ≈ 1.618)-competitive deterministic online algorithm, a (4/3 ≈ 1.33)-competitive randomized online algorithm against an oblivious adversary, and a 2-speed 1-competitive deterministic online algorithm. The analysis does not use a potential function explicitly, but instead modifies the adversary's buffer and credits the adversary to account for these modifications.

Peer-to-peer file-sharing applications suffer from a fundamental problem of unfairness. Free-riders cause slower download times for others by contributing little or no upload bandwidth while consuming much download bandwidth. Previous attempts to address this fair bandwidth allocation problem suffer from slow peer discovery, inaccurate predictions of neighboring peers' bandwidth allocations, underutilization of bandwidth, and complex parameter tuning. We present FairTorrent, a new deficit-based distributed algorithm that accurately rewards peers in accordance with their contribution. A FairTorrent peer simply uploads the next data block to a peer to whom it owes the most data as measured by a deficit counter. FairTorrent is resilient to exploitation by free-riders and strategic peers, is simple to implement, requires no bandwidth overallocation, no prediction of peers' rates, no centralized control, and no parameter tuning. We implemented FairTorrent in a BitTorrent client without modifications to the BitTorrent protocol and evaluated its performance against other widely used BitTorrent clients. Our results show that FairTorrent provides up to two orders of magnitude better fairness, up to five times better download times for contributing peers, and 60%-100% better performance on average in live BitTorrent swarms.

A common approach for dealing with large datasets is to stream over the input in one pass, and perform computations using sublinear resources. For truly massive datasets, however, even making a single pass over the data is prohibitive. Therefore, streaming computations must be distributed over many machines. In practice, obtaining significant speedups using distributed computation has numerous challenges including synchronization, load balancing, overcoming processor failures, and data distribution. Successful systems in practice such as Google's MapReduce and Apache's Hadoop address these problems by only allowing acertain classof highly distributable tasks defined by local computations that can be applied in any order to the input. The fundamental question that arises is: How does the class of computational tasks supported by these systems differ from the class for which streaming solutions exist? We introduce a simple algorithmic model for massive, unordered, distributed (mud) computation, as implemented by these systems. We show that in principle, mud algorithms are equivalent in power to symmetric streaming algorithms. More precisely, we show that any symmetric (order-invariant) function that can be computed by a streaming algorithm can also be computed by a mud algorithm, with comparable space and communication complexity. Our simulation uses Savitch's theorem and therefore has superpolynomial time complexity. We extend our simulation result to some natural classes of approximate and randomized streaming algorithms. We also give negative results, using communication complexity arguments to prove that extensions to private randomness, promise problems, and indeterminate functions are impossible. We also introduce an extension of the mud model to multiple keys and multiple rounds.

In this paper we present an experimental study of several maximum flow algorithms in the context of unbalanced bipartite networks. Our experiments are motivated by a real world problem of managing reservation-based inventory in Google content ad systems. We are interested in observing the performance of several push-relabel algorithms on our real world data sets and also on some generated ones. Previous work suggested an important improvement for push-relabel algorithms on unbalanced bipartite networks: the two-edge push rule. We show how the two-edge push rule improves the running time. While no single algorithm dominates the results, we show there is one that has very robust performance in practice.

Peer-to-Peer file-sharing applications suffer from a fundamental problem of unfairness. Free-riders cause slower download times for others by contributing little or no upload bandwidth while consuming much download bandwidth. Previous attempts to address this fair bandwidth allocation problem suffer from slow peer discovery, inaccurate predictions of neighboring peers' bandwidth allocations, underutilization of bandwidth, and complex parameter tuning. We present FairTorrent, a new deficit-based distributed algorithm that accurately rewards peers in accordance with their contribution. A FairTorrent peer simply uploads the next data block to a peer to whom it owes the most data as measured by a deficit counter. FairTorrent is resilient to exploitation by free-riders and strategic peers, is simple to implement, requires no bandwidth over-allocation, no prediction of peers' rates, no centralized control, and no parameter tuning. We implemented FairTorrent in a BitTorrent client without modifications to the BitTorrent protocol, and evaluated its performance against other widely-used BitTorrent clients. Our results show that FairTorrent provides up to two orders of magnitude better fairness, up to five times better download times for contributing peers, and 60% to 100% better performance on average in live BitTorrent swarms.

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.

The vertex cover problem is a classical NP-complete problem for which the best worst-case approximation ratio is $2-o(1)$. In this paper, we use a collection of simple graph transformations, each of which guarantees an approximation ratio of $\frac{3}{2}$, to find approximate vertex covers for a large collection of randomly generated graphs and test graphs from various sources. The graph reductions are extremely fast, and even though they by themselves are not guaranteed to find a vertex cover, we manage to find a $\frac{3}{2}$-approximate vertex cover for almost every single graph in our collection. The few graphs that we cannot solve have specific structure: they are triangle-free, with a minimum degree of at least 3, a lower bound of $\frac{n}{2}$ on the optimal vertex cover, and are unlikely to have a large bipartite subgraph.

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.

Internet search companies sell advertisement slots based on users' search queries via an auction. While there has been previous work onthe auction process and its game-theoretic aspects, most of it focuses on the Internet company. In this work, we focus on the advertisers, who must solve a complex optimization problem to decide how to place bids on keywords to maximize their return (the number of user clicks on their ads) for a given budget. We model the entire process and study this budget optimization problem. While most variants are NP-hard, we show, perhaps surprisingly, that simply randomizing between two uniform strategies that bid equally on all the keywordsworks well. More precisely, this strategy gets at least a 1-1/e fraction of the maximum clicks possible. As our preliminary experiments show, such uniform strategies are likely to be practical. We also present inapproximability results, and optimal algorithms for variants of the budget optimization problem.

We show that for low-density parity-check (LDPC) codes whose Tanner graphs have sufficient expansion, the linear programming (LP) decoder of Feldman, Karger, and Wainwright can correct a constant fraction of errors. A random graph will have sufficient expansion with high probability, and recent work shows that such graphs can be constructed efficiently. A key element of our method is the use of a dual witness: a zero-valued dual solution to the decoding linear program whose existence proves decoding success. We show that as long as no more than a certain constant fraction of the bits are flipped by the channel, we can find a dual witness. This new method can be used for proving bounds on the performance of any LP decoder, even in a probabilistic setting. Our result implies that the word error rate of the LP decoder decreases exponentially in the code length under the binary-symmetric channel (BSC). This is the first such error bound for LDPC codes using an analysis based on "pseudocodewords." Recent work by Koetter and Vontobel shows that LP decoding and min-sum decoding of LDPC codes are closely related by the "graph cover" structure of their pseudocodewords; in their terminology, our result implies that that there exist families of LDPC codes where the minimum BSC pseudoweight grows linearly in the block length

We show how the on-line bounded-space bin cover problem can be modeled with a Markov chain. We then use this Markov chain formulation to derive an algorithm for the on-line bounded-space bin cover problem. Our algorithm is designed to perform well in a restrictive environment where it can utilize only very few open bins at each time. We analyze the performance of our algorithm and compare it to the Sum-of-Squares with Threshold algorithm. The experimental results show that our algorithm compares favorably with the Sum-of-Squares with Threshold algorithm, and the average waste incurred by our algorithm is very small even when it is forced to use only a handful of open bins.

We present Grouped Distributed Queues (GDQ), the first proportional share scheduler for multiprocessor systems that scales well with a large number of processors and processes. GDQ uses a distributed queue architecture, and achieves accurate proportional fairness scheduling with only O(1) scheduling overhead. GDQ takes a novel approach to distributed queuing: instead of creating per-processor queues that need to be constantly balanced to achieve any measure of proportional sharing fairness, GDQ uses a simple grouping strategy to organize processes into groups based on similar processor time allocation rights, and then assigns processors to groups based on aggregate group shares. Group membership of processes is static, and fairness is achieved by dynamically migrating processors among groups. The set of processors working on a group use simple, low-overhead round-robin queues, while processor reallocation among groups is achieved using a new multiprocessor adaptation of Weighted Fair Queuing. By commoditizing processors and decoupling their allocation from process scheduling, GDQ provides, with only constant scheduling overhead, fairness within a constant of the ideal generalized processor sharing model for process weights with a fixed upper bound. We have implemented GDQ in Linux and measured its performance. Our experimental results show that GDQ has low overhead and scales well with the number of processors and processes.

We show that for low-density parity-check (LDPC) codes with sufficient expansion, the linear programming (LP) decoder corrects a constant fraction of errors.

Scheduling algorithms are designed to optimize many optimality criteria in a wide variety of scheduling models. To do so is well-motivated and justified, as an algorithm that works well for one scheduling problem/objective may perform poorly on a different scheduling problem/objective. In this abstract, we give very general results about the existence of schedules which simultaneously minimize two criteria. Our results are general in that they apply to almost any scheduling environment, and that they apply to all pairs of metrics in which the first metric is one of maximum flow time, makespan, or maximum lateness and the second metric is one of average flow time, average completion time, average lateness, number of on-time jobs. We will show that for almost all such pairs of metrics there exist schedules which are simultaneously close to optimal for both metrics.

We consider the problem of nonpreemptive scheduling to minimize average (weighted) completion time, allowing for release dates, parallel machines, and precedence constraints. Recent work has led to constant-factor approximations for this problem based on solving a preemptive or linear programming relaxation and then using the solution to get an ordering on the jobs. We introduce several new techniques which generalize this basic paradigm. We use these ideas to obtain improved approximation algorithms for one-machine scheduling to minimize average completion time with release dates. In the process, we obtain an optimal randomized on-line algorithm for the same problem that beats a lower bound for deterministic on-line algorithms. We consider extensions to the case of parallel machine scheduling, and for this we introduce two new ideas: first, we show that a preemptive one-machine relaxation is a powerful tool for designing parallel machine scheduling algorithms that simultaneously produce good approximations and have small running times; second, we show that a nongreedy "rounding" of the relaxation yields better approximations than a greedy one. We also prove a general theorem relating the value of one-machine relaxations to that of the schedules obtained for the original m-machine problems. This theorem applies even when there are precedence constraints on the jobs. We apply this result to obtain improved approximation ratios for precedence graphs such as in-trees, out-trees,and series-parallel graphs.

In the single-source unsplittable flow problem, we are given a network G, a source vertex s, and k commodities with sinks t i and real-valued demands $\rho_i,$ $1\leq i \leq k.$ We seek to route the demand $\rho_i$ of each commodity i along a single s-t i flow path so that the total flow routed across any edge e is bounded by the edge capacity u e . The conceptual difficulty of this NP-hard problem arises from combining packing constraints due to the existence of capacities with path selection in a graph of arbitrary topology. In this paper we give a generic framework, which yields approximation algorithms that are simpler than those previously known and achieve significant improvements upon the approximation ratios. Our framework, with appropriate subroutines, applies to all optimization versions previously considered and, unlike previous work, treats in a unified manner directed and undirected graphs. We provide extensions of our algorithms which yield the best possible approximation guarantees for restricted sets of demand values and an associated scheduling problem.

We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation schemes for several variants of this problem. Our results include PTASs for the case of identical parallel machines and a constant number of unrelated machines with and without preemption allowed. Our schemes are efficient: for all variants the running time for /spl alpha/(1+/spl epsiv/) approximation is of the form f(1//spl epsiv/, m)poly(n).

Given an undirected graph with edge costs and a subset of k 3 nodes called terminals, a multiway, or k-way, cut is a subset of the edges whose removal disconnects each terminal from the others. The multiway cut problem is to find a minimum-cost multiway cut. This problem is Max-SNP hard. Recently Calinescu, Karloff, and Rabani (STOC'98) gave a novel geometric relaxation of the problem and a rounding scheme that produced a (3=2 1=k)-approximation algorithm. In this paper, we study their geometric relaxation. In particular, we study the worst-case ratio between the value of the relaxation and the value of the minimum multicut (the so-called integrality gap of the relaxation). For k = 3, we show the integrality gap is 12=11, giving tight upper and lower bounds. That is, we exhibit a graph with integrality gap 12=11 and give an algorithm that finds a cut of value 12=11 times the relaxation value. This is the best possible performance guarantee for any algorithm based purely on the value of the relaxation and improves on Calinescu et al.'s factor of 7/6. We also improve the upper bounds for all larger values of k. For k = 4; 5, our best upper bounds are based on computer constructed and analyzed rounding schemes, while for k > 6 we give an algorithm with performance ratio 1:3438 k . Our results were discovered with the help of computational experiments that we also describe here. MIT Laboratory for Computer Science, Cambridge, MA 02138. [email protected]. Research supported by NSF contract CCR9624239, an Alfred P. Sloane Foundation Fellowship, and a David and Lucille Packard Foundation Fellowship. y Brown University . [email protected]. Research supported by NSF Grant CCR-9700146. z Dartmouth College. [email protected]. Research supported by NSF Caree...

Given a collection of strings ifS = s1, …, sn over an alphabet ∑, a superstring α of S is a string containing each si, as a substring; that is, for each i, 1⩽ i ⩽n, α contains a block of ¦si¦ consecutive characters that match si exactly. The shortest superstring problem is the problem of finding a superstring α of minimum length. The shortest superstring problem has applications in both data compression and computational biology. It was shown by Blum et al. (1994) to be MAX SNP-hard. The first O(1)-approximation algorithm also appeared in Blum et al. (1994), which returns a superstring no more than 3 times the length of an optimal solution. Prior to the algorithm described in this paper, there were several published results that improved on the approximation ratio; of these, the best was our algorithm ShortString, a 234-approximation Armen and Stein (1995). We present our new algorithm, G-ShortString, which achieves an approximation ratio of 223. Our approach builds on the work in Armen and Stein (1995) in which we identified classes of strings that have a nested periodic structure, and which must be present in the worst case for our algorithms. We introduced machinery to describe these strings and proved strong structural properties about them. In this paper we extend this study to strings that exhibit a more relaxed form of the same structure, and we use this understanding to obtain our improved result.

In the single-source unsplittable flow problem we are given a graph G, a source vertex s and a set of sinks t/sub 1/, ..., t/sub k/ with associated demands. We seek a single s-t/sub i/ flow path for each commodity i so that the demands are satisfied and the total flow routed across any edge e is bounded by its capacity c/sub e/. The problem is an NP-hard variant of max flow and a generalization of single-source edge-disjoint paths with applications to scheduling, load balancing and virtual-circuit routing problems. In a significant development, Kleinberg gave recently constant-factor approximation algorithms for several natural optimization versions of the problem. In this paper we give a generic framework, that yields simpler algorithms and significant improvements upon the constant factors. Our framework, with appropriate subroutines applies to all optimization versions previously considered and treats in a unified manner directed and undirected graphs.

) Cynthia A. Phillips Cliff Stein y Eric Torng z Joel Wein x Abstract We consider two fundamental problems in dynamic scheduling: scheduling to meet deadlines in a preemptive multiprocessor setting, and scheduling to provide good response time in a number of scheduling environments. When viewed from the perspective of traditional worst-case analysis, no good on-line algorithms exist for these problems, and for some variants no good off-line algorithms exist unless P = NP. We study these problems using a relaxed notion of competitive analysis, introduced by Kalyanasundaram and Pruhs, in which the on-line algorithm is allowed more resources than the optimal off-line algorithm to which it is compared. Using this approach, we establish that several well-known on-line algorithms, that have poor performance from an absolute worst-case perspective, are optimal for the problems in question when allowed moderately more resources. For the optimization of average flow time, these are th...

We give a distributed approximation algorithm for job scheduling in a ring architecture. In contrast to many other parallel scheduling models, the model we consider captures the influence of the underlying communications network by specifying that task migration from one processor to another takes time proportional to the distance between those two processors in the network. As a result, our algorithm must balance computational load and communication time. The algorithm is simple, requires no global control, and yields schedules of length at most 4.22 times optimal. We also give a lower bound on the performance of any distributed algorithm and the results of simulation experiments which suggest better performance than does our worst-case analysis.

Scheduling a set of tasks on a set of machines so as to yield an efficient schedule is a basic problem in computer science and operations research. Most of the research on this problem incorporates the potentially unrealistic assumption that communication between the different machines is instantaneous. In this paper we remove this assumption and study the problem of network scheduling, where each job originates at some node of a network, and in order to be processed at another node must take the time to travel through the network to that node. Our main contribution is to give approximation algorithms and hardness proofs for fully general forms of the fundamental problems in network scheduling. We consider two basic scheduling objectives: minimizing the makespan and minimizing the average completion time. For the makespan, we prove small constant factor hardness-to-approximate and approximation results. For the average completion time, we give a log-squared approximation algorithm for the most general form of the problem. The techniques used in this approximation are fairly general and have several other applications. For example, we give the first nontrivial approximation algorithm to minimize the average weighted completion time of a set of jobs on related or unrelated machines, with or without a network.

This paper present a new approach to finding minimum cuts in undirected graphs. The fundamental principle is simple: the edges in a graph's minimum cut form an extremely small fraction of the graph's edges. Using this idea, we give a randomized, strongly polynomial algorithm that finds the minimum cut in an arbitrarily weighted undirected graph with high probability. The algorithm runs in O(n 2 log 3 n) time, a significant improvement over the previous O˜(mn) time bounds based on maximum flows. It is simple and intuitive and uses no complex data structures. Our algorithm can be parallelized to run in RNC with n 2 processors; this gives the first proof that the minimum cut problem can be solved in RNC . The algorithm does more than find a single minimum cut; it finds all of them. With minor modifications, our algorithm solves two other problems of interest. Our algorithm finds all cuts with value within a multiplicative factor of α of the minimum cut's in expected O˜(n 2α ) time, or in RNC with n 2α processors. The problem of finding a minimum multiway cut of graph into r pieces is solved in expected O˜(n 2(r-1) ) time, or in RNC with n 2(r-1) processors. The “trace” of the algorithm's execution on these two problems forms a new compact data structure for representing all small cuts and all multiway cuts in a graph. This data structure can be efficiently transformed into the more standard cactus representing for minimum cuts.

All previously known algorithms for solving the multicommodity flow problem with capacities are based on linear programming. The best of these algorithms uses a fast matrix multiplication algorithm and takes O(k3.5n3m0.5 log(nDU)) time for the multicommodity flow problem with integer demands and at least O(k2.5n2m0.5 log(nϵ−1DU)) time to find an approximate solution, where k is the number of commodities, n and m denote the number of nodes and edges in the network, D is the largest demand, and U is the largest edge capacity. As a consequence, even multicommodity flow problems with just a few commodities are believed to be much harder than single-commodity maximum-flow or minimum-cost flow problems. In this paper, we describe the first polynomial-time combinatorial algorithms for approximately solving the multicommodity flow problem. The running time of our randomized algorithm is (up to log factors) the same as the time needed to solve k single-commodity flow problems, thus giving the surprising result that approximately computing a k-commodity maximum-flow is not much harder than computing about k single-commodity maximum-flows in isolation. In fact, we prove that a (simple) k-commodity flow problem can be approximately solved by approximately solving O(k log2n) single-commodity minimum-cost flow problems. Our k-commodity algorithm runs in O (knm log4n) time with high probability. We also describe a deterministic algorithm that uses an O(k)-factor more time. Given any multicommodity flow problem as input, both algorithms are guaranteed to provide a feasible solution to a modified flow problem in which all capacities are increased by a (1 + ϵ)-factor, or to provide a proof that there is no feasible solution to the original problem. We also describe faster approximation algorithms for multicommodity flow problems with a special structure, such as those that arise in "sparsest cut" problems and uniform concurrent flow problems.

This paper considers weight-maximizing variants of the classical symmetric and asymmetric traveling-salesman problems. Like their weight-minimizing counterparts, these variants are MAX SNP-hard. We present the first nontrivial approximation algorithms for these problems. Our algorithm for directed graphs finds a tour whose weight is at least 38/63/spl ap/0.603 times the weight of a maximum-weight tour, and our algorithm for undirected graphs finds a tour whose weight is at least 5/7/spl ap/0.714 times optimal. These bounds compare favorably with the 1/2 and 2/3 bounds that can be obtained for undirected and directed graphs, respectively, by simply deleting the minimum-weight edge from each cycle of a maximum-weight cycle cover. Our algorithm for directed graphs can be used to improve several recent approximation results for the shortest-superstring problem.>

We give distributed approximation algorithms for job scheduling in a ring architecture. In contrast to almost all other parallel scheduling models, the model we consider captures the influence of the underlying communications network by specifying that task migration from one processor to another takes time proportional to the distance between those two processors in the network. As a result, our algorithms must balance both computational load and communication time. The algorithms are simple, require no global control, and work in a variety of settings. All come with small constant-factor approximation guarantees; the basic algorithm yields schedules of length at most 4:22 times optimal. We also give a lower bound on the performance of any distributed algorithm and the results of simulation experiments, which give better results than our worst-case analysis. Research partially supported by NSF grant CCR-9308701, a Walter Burke Research Initiation Award and a Dartmouth College Resear...

In this paper, network flow algorithms for bipartite networks are studied. A network $G = (V,E)$ is called bipartite if its vertex set V can be partitioned into two subsets $V_1 $ and $V_2 $ such that all edges have one endpoint in $V_1 $ and the other in $V_2 $. Let $n = |V|$, $n_1 = |V_1 |$ , $n_2 = |V_2 |$, $m = |E|$ and assume without loss of generality that $n_1 \leqslant n_2 $. A bipartite network is called unbalanced if $n_1 \ll n_2 $ and balanced otherwise. (This notion is necessarily imprecise.) It is shown that several maximum flow algorithms can be substantially sped up when applied to unbalanced networks. The basic idea in these improvements is a two-edge push rule that allows one to “charge” most computation to vertices in $V_1 $, and hence develop algorithms whose running times depend on $n_1 $ rather than n. For example, it is shown that the two-edge push version of Goldberg and Tarjan’s FIFO preflow-push algorithm runs in $O(n_1 m + n_1^3 )$ time and that the analogous version of Ahuja and Orlin’s excess scaling algorithm runs in $O(n_1 m + n_1^2 \log U)$ time, where U is the largest edge capacity. These ideas are also extended to dynamic tree implementations, parametric maximum flows, and minimum-cost flows.

This paper describes new algorithms for approximately solving the concurrent multicommodity flow problem with uniform capacities. These algorithms are much faster than algorithms discovered previously. Besides being an important problem in its own right, the uniform-capacity concurrent flow problem has many interesting applications. Leighton and Rao used uniform-capacity concurrent flow to find an approximately “sparsest cut” in a graph and thereby approximately solve a wide variety of graph problems, including minimum feedback arc set, minimum cut linear arrangement, and minimum area layout. However, their method appeared to be impractical as it required solving a large linear program. This paper shows that their method might be practical by giving an $O(m^2 \log m)$ expected-time randomized algorithm for their concurrent flow problem on an m-edge graph. Raghavan and Thompson used uniform-capacity concurrent flow to solve approximately a channel width minimization problem in very large scale integration. An $O(k^{{3 / 2}} (m + n\log n)$ expected-time randomized algorithm and an $O(k\min \{ n,k\} (m + n\log n)\log k)$ deterministic algorithm is given for this problem when the channel width is $\Omega (\log n)$, where k denotes the number of wires to be routed in an n-node, m-edge network.

In the job shop scheduling problem, there are m machines and n jobs. A job consists of a sequence of operations, each of which must be processed on a specified machine, and the aim is to complete all jobs as quickly as possible. This problem is strongly .$\mathcal{NP}$-hard even for very restrictive special cases. The authors give the first randomized and deterministic polynomial-time algorithms that yield polylogarithmic approximations to the optimal length schedule. These algorithms also extend to the more general case where a job is given not by a linear ordering of the machines on which it must be processed but by an arbitrary partial order. Comparable bounds can also be obtained when there are $m'$ types of machines, a specified number of machines of each type, and each operation must be processed on one of the machines of a specified type, as well as for the problem of scheduling unrelated parallel machines subject to chain precedence constraints.

Article An Õ(n2) algorithm for minimum cuts Share on Authors: David R. Karger View Profile , Clifford Stein View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 757–765https://doi.org/10.1145/167088.167281Online:01 June 1993Publication History 35citation853DownloadsMetricsTotal Citations35Total Downloads853Last 12 Months22Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

All previously known algorithms for solving the multicommodity flow problem with capacities are based on linear programming.The best of these algorithms [14] uses a fast matrix multiplication algorithm and takes O(k25n2m5 log(nDU))time to find an approximate solution, where k is the number of commodities, n and m denote the number of nodes and edges in the network, D is the largest demand, and U is the largest edge capacity.Substantially more time is needed to find an exact solution.As a consequence, even multicommodit y flow problems with jnst a few commodities are believed to be much harder than single-commodity maximum-flow or minimum-cost flow problems.In thk paper, we describe the first polynomial-time combinatorial algorithms for approximately solving the multicommodity flow problem.The running time of our randomized algorithm is (up to ,log factors) the same as the time needed to solve k single-commodity flow problems, thus giving the surprising result that approximately computing a k-commodity maximum-flow is not much harder than computing about k single-commodity maximum-flows in isolation.In fact, we prove that a (simple) k-commodity flow problem can be approximately solved by approximately solving O(k log2 n) single-commodity minimum-cost flow problems.Our k-commodity algorithm runs in O(knm log4 n) time with high probability.We also describe a deterministic algorithm that uses an O(k)-factor more time.Given any multicommodit y flow problem as input, both rdgorithms are guaranteed to provide a feasible solution to a modified @ 1991

In this paper, we describe new algorithms for approximately solving the concurrent multicommodity flow problem with uniform capacities.Our algorithms are much faster than previously known algorithms.Besides being an important problem in its own right, the concurrent flow problem has many interesting applications.Leighton and Rao used concurrent flow to find an approximately "sparsest cut" in a graph, and thereby approximately solve a wide variety of graph problems, including minimum feedback arc set, minimum cut linear arrangement, and minimum area layout.We show that their method might be practical by giving an O(m~logm) expected-time randomized algorithm for their concurrent flow problem on an m-edge graph.l~aghavan and Thompson used concurrent flow to approximately solve a channel width minimization problem in VLSI.We give an O(k3/2(m+n log n)) expectedtime randomized algorithm and an O(k min{n, k}(m + n log n) log k) deterministic algorithm for this problem when the channel width is O(logn), where k denotes the number of wires to be routed in an n-node, m-edge network,