ACM Transactions on Algorithms

Given a weighted planar bipartite graph G(A ∪ B, E) where each edge has an integer edge cost, we give an Õ(n^4/3log nC) time algorithm to compute minimum-cost perfect matching; here C is the maximum edge cost in the graph. The previous best-known ...

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

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

We consider integer programming problems in standard form max { c^Tx : Ax = b, x⩾ 0, x ∈ Zⁿ} where A ∈ Z^{m × n}, b ∈ Z^m, and c ∈ Zⁿ. We show that such an integer program can be solved in time (m ⋅ Δ)^O(m) ⋅ \Vert b\Vert_∞², where Δ is an upper bound on each ...

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

This article presents an algorithm that solves the 3SUM problem for n real numbers in O((n²/ log²n)(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 ...

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

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

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

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

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

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 + √ n) time and ...

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

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