We present a new scaling algorithm for maximum (or minimum) weight perfect matching on general, edge weighted graphs. Our algorithm runs in $O(m\sqrt{n}\log(nN))$ time, $O(m\sqrt{n})$ per scale, which matches the running time of the best cardinality matching algorithms on sparse graphs. Here $m,n,$ and $N$ bound the number of edges, vertices, and magnitude of any integer edge weight. Our result improves on a 25-year old algorithm of Gabow and Tarjan, which runs in $O(m\sqrt{n\log n\alpha(m,n)} \log(nN))$ time.

The Firefighter problem and a variant of it, known as Resource Minimization for Fire Containment (RMFC), are natural models for optimal inhibition of harmful spreading processes. Despite considerable progress on several fronts, the approximability of these problems is still badly understood. This is the case even when the underlying graph is a tree, which is one of the most-studied graph structures in this context and the focus of this paper. In their simplest version, a fire spreads from one fixed vertex step by step from burning to adjacent non-burning vertices, and at each time step B many non-burning vertices can be protected from catching fire. The Firefighter problem asks, for a given B, to maximize the number of vertices that will not catch fire, whereas RMFC (on a tree) asks to find the smallest B that allows for saving all leaves of the tree. Prior to this work, the best known approximation ratios were an O(1)-approximation for the Firefighter problem and an O(log^* n)-approximation for RMFC, both being LP-based and essentially matching the integrality gaps of two natural LP relaxations. We improve on both approximations by presenting a PTAS for the Firefighter problem and an O(1)-approximation for RMFC, both qualitatively matching the known hardness results. Our results are obtained through a combination of the known LPs with several new techniques, which allow for efficiently enumerating over super-constant size sets of constraints to strengthen the natural LPs.

We consider the classical selection and sorting problems in a model where the initial permutation of the input has to be restored after completing the computation. While the requirement of the restoration is stringent compared to the classical versions of the problems, this model is more relaxed than a read-only memory (ROM) where the input elements are not allowed to be moved within the input array. We fi rst show that for a sequence of n integers, selection ( finding the median or more generally the k-th smallest element for a given k) can be done in O(n) time using O(lg n) words. In contrast, no linear-time selection algorithm is known which uses polylogarithmic space in ROM. For sorting n integers in this model, we fi rst present an O(n lg n)-time algorithm using O(lg n) words. When the universe size U is polynomial in n, we give a faster O(n)-time algorithm (analogous to radix sort) which uses O(n^eps) words of extra space for an arbitrarily small constant eps > 0. More generally, we show how to match the time bound of any word-RAM integer-sorting algorithms using O(n^eps) words of extra space. In sharp contrast, there is an (n^2/S)-time lower bound for integer sorting using O(S) space in ROM. For indivisible input elements, we prove the same lower bound for sorting in our model. En route, we develop linear-time in-place algorithms to extract leading bits of the input and to compress and decompress strings with low entropy.

Chazelle and Matou\v sek [\emph{J. Algorithms}, 1996] presented a derandomization of Clarkson's sampling-based algorithm [\emph{J. ACM}, 1995] for solving linear programs with $n$ constraints and $d$ variables in $d^{(7+o(1))d}n$ deterministic time. The time bound can be improved to $d^{(5+o(1))d}n$ with subsequent work by Br\"onnimann, Chazelle, and Matou\v sek [\emph{SIAM J. Comput.}, 1999]. We first point out a much simpler derandomization of Clarkson's algorithm that avoids $\eps$-approximations and runs in $d^{(3+o(1))d}n$ time. We then describe a few additional ideas that eventually improve the deterministic time bound to $d^{(1/2+o(1))d}n$.

We present the buffer heap, a cache-oblivious priority queue that supports Delete-Min, Delete and a hybrid Insert/Decrease-Key operation in $\Oh{\frac{1}{B}\log_{2}{\frac{N}{M}}}$ amortized cache-misses, where $M$ and $B$ are the (unknown) cache-size and block-size, respectively, and $N$ is the number of elements in the queue. We introduce the notion of a slim data structure which captures the situation when only a limited portion of the cache which we call a slim cache, is available to the data structure to retain data between data structural operations. We show that a buffer heap automatically adapts to such an environment and supports all operations in $\Oh{\frac{1}{\lam}+\frac{1}{B}\log_{2}{\frac{N}{\lam}}}$ amortized cache-misses each when the slim cache size is $\lam$. Our results provide substantial improvements over known trivial cache performance bounds for cache-oblivious priority queues with Decrease-Keys. Using the buffer heap we present cache-oblivious implementations of Dijkstra's SSSP algorithm for undirected and directed graphs with non-negative real edge-weights. On a graph with $n$ vertices and $m$ edges, our algorithm for the undirected case incurs $\Oh{n+\frac{m}{B}\log_{2}{\frac{n}{M}}}$ cache-misses and for the directed case causes $\Oh{\left(n+\frac{m}{B}\right)\cdot\log_{2}{\frac{n}{B}}}$ cache-misses. These results give the first non-trivial cache-oblivious bounds for the SSSP problem on general graphs. For the APSP problem on weighted undirected graphs, we incorporate slim buffer heaps into multi-buffer-heaps and use these to improve the cache-aware cache complexity. We also present a simple cache-oblivious APSP algorithm for unweighted undirected graphs that incurs $O(\frac{mn}{B}\log_{M/B}\frac{n}{B})$ cache-misses. This matches the cache-aware bound and is a substantial improvement over the previous cache oblivious bound for the problem.

We consider a new construction of locality-sensitive hash functions for Hamming space that is covering in the sense that is it guaranteed to produce a collision for every pair of vectors within a given radius r. The construction is efficient in the sense that the expected number of hash collisions between vectors at distance cr, for a given c>1, comes close to that of the best possible data independent LSH without the covering guarantee, namely, the seminal LSH construction of Indyk and Motwani (STOC '98). The efficiency of the new construction essentially matches their bound when the search radius is not too large --- e.g., when cr = o(log(n)/log log n), where n is the number of points in the data set, and when cr = log(n)/k where k is an integer constant. In general, it differs by at most a factor ln(4) in the exponent of the time bounds. As a consequence, LSH-based similarity search in Hamming space can avoid the problem of false negatives at little or no cost in efficiency.

We consider the minimum-load k-facility location (MLKFL) problem: give a set F of facilities, a set C of clients, and an integer k\geq 0, and a distance function d(f,j). The goal is to open a set F'\subseteq F of k facilities, and assign each client j to a facility f(j)\in F so as to minimize \max_{f\in F}\sum_{j\in C:f(j)=f}d(f,j). This problem was studied under the name of min-max star cover in {EGK+03,AHL06}, who gave bicriteria approximation algorithms for when F=C. MLKFL is rather poorly understood, and only an $O(k)$-approximation is currently known even for line metrics. Our main result is a PTAS for MLKFL on line metrics. Complementing this, we prove that MLKFL is strongly NP-hard on line metrics. We also devise a QPTAS for it on tree metrics. MLKFL turns out to be surprisingly challenging even on line metrics; we show that: (a) even a configuration-style LP has a bad integrality gap; and (b) a multi-swap local-search heuristic has a bad locality gap. Our PTAS for line metrics consists of two main ingredients. First, we prove existence of a near-optimal solution possessing some nice properties. A novel aspect of this proof is that we first move to a mixed-integer LP (MILP), and argue that a MILP-solution minimizing a certain potential function possesses the desired structure, and then use a rounding algorithm for the generalized-assignment problem to ``transfer'' this structure to the rounded integer solution. We then show how to find a solution having these structural properties using DP.

This paper addresses the problem of designing a {\em fault-tolerant} $(\alpha, \beta)$ approximate BFS structure (or {\em FT-ABFS structure} for short), namely, a subgraph $H$ of the network $G$ such that subsequent to the failure of some subset $F$ of edges or vertices, the surviving part %$H'$ of $H$ still contains an \emph{approximate} BFS spanning tree for (the surviving part of) $G$, satisfying $\dist(s,v,H\setminus F) \leq \alpha \cdot \dist(s,v,G\setminus F)+\beta$ for every $v \in V$. In SODA'14, we considered {\em multiplicative} $(\alpha,0)$ FT-ABFS structures resilient to a failure of a \emph{single} edge and presented an algorithm that given an $n$-vertex unweighted undirected graph $G$ and a source $s$ constructs a $(3,0)$ FT-ABFS structure rooted at $s$ with at most $4n$ edges (improving by an $O(\log n)$ factor on the near-tight result of \cite{BS10} for the special case of edge failures). Assuming at most $f$ edge failures, for constant integer $f>1$, we prove that there exists a (poly-time constructible) $(3(f+1), (f+1) \log n)$ FT-ABFS structure with $O(f n)$ edges. %%resilient to the failure of up to $f$ edges. We then consider {\em additive} $(1,\beta)$ FT-ABFS structures and demonstrate an interesting dichotomy between multiplicative and additive spanners. In contrast to the linear size of $(\alpha,0)$ FT-ABFS structures, we show that for every $\beta \in [1, O(\log n)]$ there exists an $n$-vertex graph $G$ with a source $s$ for which any $(1,\beta)$ FT-ABFS structure rooted at $s$ has $\Omega(n^{1+\epsilon(\beta)})$ edges, for some function $\epsilon(\beta) \in (0,1)$.

We study the problem of maintaining a breadth-first spanning tree (BFS tree) in partially dynamic distributed networks modeling a sequence of either failures or additions of communication links (but not both). We show deterministic (1+[)-approximation algorithms whose amortized time (over some number of link changes) is sublinear in D, the maximum diameter of the network. Our technique also leads to a deterministic (1+[)-approximate incremental algorithm for single-source shortest paths (SSSP) in the sequential (usual RAM) model. Prior to our work, the state of the art was the classic exact algorithm of Even and Shiloach [1981] that is optimal under some assumptions [Roditty and Zwick 2011; Henzinger et al. 2015]. Our result is the first to show that, in the incremental setting, this bound can be beaten in certain cases if a small approximation is allowed.

For any integer $n\geq 1$ a \emph{middle levels Gray code} is a cyclic listing of all bitstrings of length $2n+1$ that have either $n$ or $n+1$ entries equal to 1 such that any two consecutive bitstrings in the list differ in exactly one bit. The question whether such a Gray code exists for every $n\geq 1$ has been the subject of intensive research during the last 30 years, and has been answered affirmatively only recently [T.~Mütze. Proof of the middle levels conjecture. \textit{arXiv:1404.4442}, 2014]. In this work we provide the first efficient algorithm to compute a middle levels Gray code. For a given bitstring, our algorithm computes the next $\ell$ bitstrings in the Gray code in time $\cO(n\ell(1+\frac{n}{\ell}))$, which is $\cO(n)$ on average per bitstring provided that $\ell=\Omega(n)$.

Let $M=(E, \mathcal{I})$ be a matroid of rank $n$. A {\em $k$-truncation} of $M$ is a matroid {$M'=(E,{\mathcal I}')$} such that for any $A\subseteq E$, $A\in {\mathcal2 I}'$ if and only if $|A|\leq k$ and $A\in \I$. Given a linear representation, $A$, of $M$ we consider the problem of finding a linear representation, $A_k$, of the $k$-truncation of $M$. A common way to compute $A_k$ is to multiply the matrix $A$ with a random $k\times n$ matrix, yielding a simple randomized algorithm. So a natural question is whether we can compute $A_k$ {\em deterministically}. In this paper we settle this question for matrices over any field in which the field operations can be done efficiently. This includes any finite field and the field of rational numbers ($\mathbb Q$). Our algorithms are based on the properties of the classical Wronskian determinant, and the folded Wronskian determinant, which was recently introduced by Guruswami and Kopparty~[\,{\em FOCS, 2013; COMBINATORICA 2016}\,], and Forbes and Shpilka~[\,{\em STOC, 2012}\,]. Our main conceptual contribution in this paper is to show that the Wronskian determinant can also be used to obtain a representation of the truncation of a linear matroid in deterministic polynomial time. Finally, we use our results to derandomize several parameterized algorithms, including an algorithm for computing {\sc $\ell$-Matroid Parity}, to which several problems, such as {\sc $\ell$-Matroid Intersection}, can be reduced.

We study the problem of detecting {\em outlier pairs} of strongly correlated variables among a collection of $n$ variables with otherwise weak pairwise correlations. After normalization, this task amounts to the geometric task where we are given as input a set of $n$ vectors with unit Euclidean norm and dimension $d$, and we are asked to find all the outlier pairs of vectors whose inner product is at least $\rho$ in absolute value, subject to the promise that all but at most $q$ pairs of vectors have inner product at most $\tau$ in absolute value for some constants $0<\tau<\rho<1$. Improving on an algorithm of G.~Valiant [FOCS~2012; J.\,ACM~2015], we present a randomized algorithm that for Boolean inputs ($\{-1,1\}$-valued data normalized to unit Euclidean length) runs in time \[ \tilde O\bigl(n^{\max\,\{1-\gamma+M(\Delta\gamma,\gamma),\,M(1-\gamma,2\Delta\gamma)\}}+qdn^{2\gamma}\bigr)\,, \] where $0<\gamma<1$ is a constant tradeoff parameter and $M(\mu,\nu)$ is the exponent to multiply an $\lfloor n^\mu\rfloor\times\lfloor n^\nu\rfloor$ matrix with an $\lfloor n^\nu\rfloor\times \lfloor n^\mu\rfloor$ matrix and $\Delta=1/(1-\log_\tau\rho)$. As corollaries we obtain randomized algorithms that run in time \[ \tilde O\bigl(n^{\frac{2\omega}{3-\log_\tau\rho}}+qdn^{\frac{2(1-\log_\tau\rho)}{3-\log_\tau\rho}}\bigr) \] and in time \[ \tilde O\bigl(n^{\frac{4}{2+\alpha(1-\log_\tau\rho)}}+qdn^{\frac{2\alpha(1-\log_\tau\rho)}{2+\alpha(1-\log_\tau\rho)}}\bigr)\,, \] where $2\leq\omega<2.38$ is the exponent for square matrix multiplication and $0.3<\alpha\leq 1$ is the exponent for\, rectangular matrix multiplication. We present further corollaries for the light bulb problem and for learning sparse Boolean functions. (The notation {$\tilde O(\cdot)$} hides polylogarithmic factors in $n$ and $d$ whose degree may depend on $\rho$ and $\tau$.)

We present a deterministic incremental algorithm for \textit{exactly} maintaining the size of a minimum cut with $\widetilde{O}(1)$ amortized time per edge insertion and $O(1)$ query time. This result partially answers an open question posed by Thorup [Combinatorica 2007]. It also stays in sharp contrast to a polynomial conditional lower-bound for the fully-dynamic weighted minimum cut problem. Our algorithm is obtained by combining a recent sparsification technique of Kawarabayashi and Thorup [STOC 2015] and an exact incremental algorithm of Henzinger [J. of Algorithm 1997]. We also study space-efficient incremental algorithms for the minimum cut problem. Concretely, we show that there exists an ${O}(n\log n/\varepsilon^2)$ space Monte-Carlo algorithm that can process a stream of edge insertions starting from an empty graph, and with high probability, the algorithm maintains a $(1+\varepsilon)$-approximation to the minimum cut. The algorithm has $\widetilde{O}(1)$ amortized update-time and constant query-time.

We obtain a number of lower bounds on the running time of algorithms solving problems on graphs of bounded treewidth. We prove the results under the Strong Exponential Time Hypothesis of Impagliazzo and Paturi. In particular, assuming that SAT cannot be solved in (2-\epsilon)^{n}m^{O(1)} time, we show that for any e > 0; {\sc Independent Set} cannot be solved in (2-e)^{tw(G)}|V(G)|^{O(1)} time, {\sc Dominating Set} cannot be solved in (3-e)^{tw(G)}|V(G)|^{O(1)} time, {\sc Max Cut} cannot be solved in (2-e)^{tw(G)}|V(G)|^{O(1)} time, {\sc Odd Cycle Transversal} cannot be solved in (3-e)^{tw(G)}|V(G)|^{O(1)} time, For any qe 3, q-{\sc Coloring} cannot be solved in (q-e)^{tw(G)}|V(G)|^{O(1)} time, {\sc Partition Into Triangles} cannot be solved in (2-e)^{tw(G)}|V(G)|^{O(1)} time. Our lower bounds match the running times for the best known algorithms for the problems, up to the e in the base.

We consider the problem of online scheduling of jobs on unrelated machines with dynamic speed scaling to minimize the sum of energy and weighted flow time. We give an algorithm with an almost optimal competitive ratio for arbitrary power functions. (No earlier results handled arbitrary power functions for unrelated machines.) For power functions of the form f(s) = s^± for some constant ± > 1, we get a competitive ratio of O(±/log ±), improving upon a previous competitive ratio of O(±^2) by [Anand et al. 2012], along with a matching lower bound of ©(±/log ±). Further, in the resource augmentation model, with a 1+µ speed up, we give a 2(1/µ+1) competitive algorithm, with essentially the same techniques, improving the bound of 1 + O(1/µ^2) by [Gupta et al. 2010] and matching the bound of [Anand et al. 2012] for the special case of fixed speed unrelated machines. Unlike the previous results most of which used an amortized local competitiveness argument or dual fitting methods, we use a primal-dual method, which is useful not only to analyze the algorithms but also to design the algorithm itself.

We consider a distributed private data analysis setting, where multiple parties each hold some sensitive data; and they wish to run a protocol to learn some aggregate statistics over the distributed dataset, while protecting each user's privacy. As an initial effort, we consider a distributed summation problem. We first show a lower bound, i.e., under information-theoretic differential privacy, any multi-party protocol with a small number of messages must have large additive error. We then show that by adopting a computational differential privacy notion, one can circumvent this lower-bound, and design practical protocols for the periodic distributed summation problem. Our construction has several desirable features. First, it works in the client-server model, and requires no peer-to-peer communication among the clients. Second, our protocol is fault tolerant, and can output meaningful statistics even when a subset of the participants fail to respond. Our constructions guarantee the privacy of honest parties even when a fraction of the participants may be compromised and colluding. In addition, we propose a new distributed noise addition mechanism that guarantees small total error.

We prove the first non-trivial performance ratio strictly above 0.5 for the weighted Ranking algorithm on the oblivious matching problem where nodes in a general graph can have arbitrary weights. We have discovered a new structural property of the ranking algorithm: if a node has two unmatched neighbors, then it will still be matched even when its rank is demoted to the bottom. This property allows us to form LP constraints for both the weighted and the unweighted versions of the problem. Using a new class of continuous LP, we prove that the ratio for the weighted case is at least 0.501512, and improve the ratio for the unweighted case to 0.526823 (from the previous best 0.523166 in SODA 2014). Unlike previous continuous LP in which the primal solution must be continuous everywhere, our new continuous LP framework allows the monotone component of the primal function to have jump discontinuities, and the other primal components to take non-conventional forms such as the Dirac delta function.

We consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find a shortest tour that visits each of a given collection of subsets (regions or neighborhoods) in the underlying metric space. We give a randomized polynomial time approximation scheme (PTAS) when the regions are fat weakly disjoint. This notion of regions was first defined when a QPTAS was given for the problem in [SODA 2010: Chan and Elbassioni]. We combine the techniques in the previous work, together with the recent PTAS for TSP [STOC 2012: Bartal, Gottlieb and Krauthgamer] to achieve a PTAS for TSPN. However, several non-trivial technical hurdles need to be overcome for applying the PTAS framework to TSPN. (1) Heuristic to detect sparse instances. In the STOC 2012 paper, a minimum spanning tree heuristic is used to estimate the portion of an optimal tour within some ball. However, for TSPN, it is not known if an optimal tour would use points inside the ball to visit regions that intersect the ball. (2) Partially cut regions in the recursion. After a sparse ball is identified by the heuristic, the PTAS framework for TSP uses dynamic program to solve the instance restricted to the sparse ball, and recursively solve the remaining instance. However, for TSPN, it is an important issue to decide whether each region partially intersecting the sparse ball should be solved in the sparse instance or considered in the remaining instance.

We give the first linear kernels for Dominating Set and Connected Dominating Set problems on graphs excluding a fixed graph $H$ as a topological minor. Our results extend the known classes of graphs on which Dominating Set and Connected Dominating Set problems admit linear kernels. Prior to our work, it was known that these problems admit linear kernels on graphs excluding a fixed apex graph $H$ as a minor. Moreover, for Dominating Set, a kernel of size $k^{c(H)}$, where $c(H)$ is a constant depending on the size of $H$, follows from a more general result on the kernelization of Dominating Set on graphs of bounded degeneracy. Alon and Gutner asked explicitly, whether one can obtain a linear kernel for Dominating Set on $H$-minor free, graphs. We answer this question in affirmative and in fact prove a more general result. Our kernelization algorithm is based on a non-trivial combination of the following ingredients (a) the structural theorem of Grohe and Marx [STOC 2012] for graphs excluding a fixed graph $H$ as a topological subgraph; (b) A novel notion of protrusions, different that the one defined in [FOCS 2009]; and (c) Our results are based on a generic reduction rule producing an equivalent instance of the problem with treewidth $O(\sqrt{k})$. The application of this rule in a divide-and-conquer fashion together with new notion of protrusions brings us to linear kernels. We believe that the new notion of protrusion will be useful in many other algorithmic settings.

In the Subset Feedback Vertex Set (Subset FVS) problem, the input is a graph G on n vertices and m edges, a subset of vertices T, referred to as terminals, and an integer k. The objective is to determine whether there exists a set of at most k vertices intersecting every cycle that contains a terminal. The study of parameterized algorithms for this generalization of the Feedback Vertex Set problem has received significant attention over the last few years. In fact the parameterized complexity of this problem was open until 2011, when two groups independently showed that the problem is fixed parameter tractable (FPT). However, the existence of an FPT algorithm with a linear dependence on the input size has remained open. In this paper we design the first linear time parameterized algorithms for Subset FVS. More precisely, we obtain the following new algorithms for Subset FVS. " A randomized algorithm for Subset FVS running in time O(25.6^k · (n + m)). " A deterministic algorithm for Subset FVS running in time 2^{O(k log k)} · (n + m). In particular, the first algorithm obtains the best possible dependence on both the parameter as well as the input size, up to the constant in the exponent. Both of our algorithms are based on cut centrality, in the sense that solution vertices are likely to show up in minimum size cuts between vertices sampled from carefully chosen distributions.