The distinct elements problem is one of the fundamental problems in streaming algorithms—given a stream of integers in the range { 1,… ,n}, we wish to provide a (1+ϵ) approximation to the number of distinct elements in the input. After a long line of research an optimal solution for this problem with constant probability of success, using O(1/ϵ2+lg n) bits of space, was given by Kane, Nelson, and Woodruff in 2010. The standard approach used to achieve low failure probability Δ is to take the median of lg Δ−1 parallel repetitions of the original algorithm. We show that such a multiplicative space blow-up is unnecessary: We provide an optimal algorithm using O(lg Δ−1/ϵ2 + lg n) bits of space—matching known lower bounds for this problem. PubDate: Thu, 05 Dec 2019 00:00:00 GMT

We provide a tight analysis that settles the round complexity of the well-studied parallel randomized greedy MIS algorithm, thus answering the main open question of Blelloch, Fineman, and Shun [SPAA’12]. The parallel/distributed randomized greedy Maximal Independent Set (MIS) algorithm works as follows. An order of the vertices is chosen uniformly at random. Then, in each round, all vertices that appear before their neighbors in the order are added to the independent set and removed from the graph along with their neighbors. The main question of interest is the number of rounds it takes until the graph is empty. This algorithm has been studied since 1987, initiated by Coppersmith, Raghavan, and Tompa [FOCS’87], and the previously best known bounds were O(log n) rounds in expectation for Erdős-Rényi random graphs by Calkin and Frieze [Random Struc. PubDate: Thu, 05 Dec 2019 00:00:00 GMT

The weighted k-server problem is a generalization of the k-server problem wherein the cost of moving a server of weight βi through a distance d is βiṡ d. On uniform metric spaces, this models caching with caches having different page replacement costs. A memoryless algorithm is an online algorithm whose behavior is independent of the history given the positions of its k servers. In this article, we develop a framework to analyze the competitiveness of randomized memoryless algorithms. The key technical contribution is a method for working with potential functions defined implicitly as the solution of a linear system. Using this, we establish tight bounds on the competitive ratio achievable by randomized memoryless algorithms for the weighted k-server problem on uniform metrics. PubDate: Thu, 05 Dec 2019 00:00:00 GMT

Abstract: Fabrizio Grandoni, Virginia Vassilevska Williams

Shortest paths computation is one of the most fundamental problems in computer science. An important variant of the problem is when edges can fail, and one needs to compute shortest paths that avoid a (failing) edge. More formally, given a source node s, a target node t, and an edge e, a replacement path for the triple (s,t,e) is a shortest s-t path avoiding edge e. Replacement paths computation can be seen either as a static problem or as a data structure problem. In the static setting, a typical goal is to compute for fixed s and t, for every possible failed edge e, the length of the best replacement path around e (replacement paths problem). PubDate: Thu, 05 Dec 2019 00:00:00 GMT

Given a weighted planar bipartite graph G(A ∪ B, E) where each edge has an integer edge cost, we give an Õ(n4/3log nC) time algorithm to compute minimum-cost perfect matching; here C is the maximum edge cost in the graph. The previous best-known planarity exploiting algorithm has a running time of O(n3/2log n) and is achieved by using planar separators (Lipton and Tarjan ’80). Our algorithm is based on the bit-scaling paradigm (Gabow and Tarjan ’89). For each scale, our algorithm first executes O(n1/3) iterations of Gabow and Tarjan’s algorithm in O(n4/3) time leaving only O(n2/3) vertices unmatched. Next, it constructs a compressed residual graph H with O(n2/3) vertices and O(n) edges. PubDate: Fri, 15 Nov 2019 00:00:00 GMT

We give an new arithmetic algorithm to compute the generalized Discrete Fourier Transform (DFT) over finite groups G. The new algorithm uses O(∣G∣ω /2 + o(1)) operations to compute the generalized DFT over finite groups of Lie type, including the linear, orthogonal, and symplectic families and their variants, as well as all finite simple groups of Lie type. Here ω is the exponent of matrix multiplication, so the exponent ω/2 is optimal if ω = 2. Previously, “exponent one” algorithms were known for supersolvable groups and the symmetric and alternating groups. No exponent one algorithms were known, even under the assumption ω = 2, for families of linear groups of fixed dimension, and indeed the previous best-known algorithm for SL2(Fq) had exponent 4/3 despite being the focus of significant effort. PubDate: Fri, 15 Nov 2019 00:00:00 GMT

We consider integer programming problems in standard form max { cTx : Ax = b, x⩾ 0, x ∈ Zn} where A ∈ Zm × n, b ∈ Zm, and c ∈ Zn. We show that such an integer program can be solved in time (m ṡ Δ)O(m) ṡ \Vert b\Vert∞2, where Δ is an upper bound on each absolute value of an entry in A. This improves upon the longstanding best bound of Papadimitriou [27] of (mṡ Δ)O(m2), where in addition, the absolute values of the entries of b also need to be bounded by Δ. Our result relies on a lemma of Steinitz that states that a set of vectors in Rm that is contained in the unit ball of a norm and that sum up to zero can be ordered such that all partial sums are of norm bounded by m. PubDate: Fri, 15 Nov 2019 00:00:00 GMT

This article presents an algorithm that solves the 3SUM problem for n real numbers in O((n2/ log2n)(log log n)O(1)) time, improving previous solutions by about a logarithmic factor. Our framework for shaving off two logarithmic factors can be applied to other problems, such as (median,+)-convolution/matrix multiplication and algebraic generalizations of 3SUM. This work also obtains the first subquadratic results on some 3SUM-hard problems in computational geometry, for example, deciding whether (the interiors of) a constant number of simple polygons have a common intersection. PubDate: Fri, 15 Nov 2019 00:00:00 GMT

The complexity of distributed edge coloring depends heavily on the palette size as a function of the maximum degree Δ. In this article, we explore the complexity of edge coloring in the LOCAL model in different palette size regimes. Our results are as follows. Lower Bounds: First, we simplify the round elimination technique of Brandt et al. [16] and prove that (2Δ −2)-edge coloring requires Ω (logΔ log n) time with high probability and Ω (logΔ n) time deterministically, even on trees. Second, we show that a natural approach to computing (Δ +1)-edge colorings (Vizing’s theorem), namely, extending an arbitrary partial coloring by iteratively recoloring subgraphs, requires Ω (Δ log n) time. PubDate: Fri, 15 Nov 2019 00:00:00 GMT

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. PubDate: Fri, 15 Nov 2019 00:00:00 GMT

Abstract: Brian Brubach, Karthik A. Sankararaman, Aravind Srinivasan, Pan Xu

Column-sparse packing problems arise in several contexts in both deterministic and stochastic discrete optimization. We present two unifying ideas, (non-uniform) attenuation and multiple-chance algorithms, to obtain improved approximation algorithms for some well-known families of such problems. As three main examples, we attain the integrality gap, up to lower-order terms, for known LP relaxations for k-column-sparse packing integer programs (Bansal et al., Theory of Computing, 2012) and stochastic k-set packing (Bansal et al., Algorithmica, 2012), and go “half the remaining distance” to optimal for a major integrality-gap conjecture of Füredi, Kahn, and Seymour on hypergraph matching (Combinatorica, 1993). PubDate: Fri, 15 Nov 2019 00:00:00 GMT

Knuth assigned the following open problem a difficulty rating of 48/50 in The Art of Computer Programming Volume 4A: For odd n ≥ 3, can the permutations of { 1,2,… , n} be ordered in a cyclic list so that each permutation is transformed into the next by applying either the operation σ, a rotation to the left, or τ, a transposition of the first two symbols' The Sigma-Tau problem is equivalent to finding a Hamilton cycle in the directed Cayley graph generated by σ = (1 2 ṡ n) and τ = (1 2). PubDate: Fri, 15 Nov 2019 00:00:00 GMT

Abstract: Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh

We provide a randomized linear time approximation scheme for a generic problem about clustering of binary vectors subject to additional constraints. The new constrained clustering problem generalizes a number of problems and by solving it, we obtain the first linear time-approximation schemes for a number of well-studied fundamental problems concerning clustering of binary vectors and low-rank approximation of binary matrices. Among the problems solvable by our approach are Low GF(2)-Rank Approximation, Low Boolean-Rank Approximation, and various versions of Binary Clustering. For example, for Low GF(2)-Rank Approximation problem, where for an m× n binary matrix A and integer r> 0, we seek for a binary matrix B of GF(2) rank at most r such that the ℓ0-norm of matrix A−B is minimum, our algorithm, for any ε > 0 in time f(r,ε)ṡ nṡ m, where f is some computable function, outputs a (1+ε)-approximate solution with probability at least (1−1\e). PubDate: Fri, 15 Nov 2019 00:00:00 GMT

Abstract: Gopal Pandurangan, Peter Robinson, Michele Scquizzato

This article presents a randomized (Las Vegas) distributed algorithm that constructs a minimum spanning tree (MST) in weighted networks with optimal (up to polylogarithmic factors) time and message complexity. This algorithm runs in Õ(D + &sqrt; n) time and exchanges Õ(m) messages (both with high probability), where n is the number of nodes of the network, D is the hop-diameter, and m is the number of edges. This is the first distributed MST algorithm that matches simultaneously the time lower bound of Ω˜(D + &sqrt; n) [10] and the message lower bound of Ω (m) [31], which both apply to randomized Monte Carlo algorithms. PubDate: Fri, 15 Nov 2019 00:00:00 GMT