ACM DL

ACM Transactions on

Algorithms (TALG)

Menu
Latest Articles

A Faster Algorithm for Minimum-cost Bipartite Perfect Matching in Planar Graphs

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... (more)

A New Algorithm for Fast Generalized DFTs

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... (more)

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

We consider integer programming problems in standard form max { cTx : Ax = b, x⩾ 0, x ∈ Zn} where A ∈ Zm × n, b... (more)

More Logarithmic-factor Speedups for 3SUM, (median,+)-convolution, and Some Geometric 3SUM-hard Problems

This article presents an algorithm that solves the 3SUM problem for n real numbers in O((n2/... (more)

Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma

The complexity of distributed edge coloring depends heavily on the palette size as a function of the maximum degree Δ. In this article, we... (more)

Scheduling When You Do Not Know the Number of Machines

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... (more)

Algorithms to Approximate Column-sparse Packing Problems

Column-sparse packing problems arise in several contexts in both deterministic and stochastic discrete optimization. We present two unifying ideas,... (more)

Solving the Sigma-Tau Problem

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... (more)

Approximation Schemes for Low-rank Binary Matrix Approximation Problems

We provide a randomized linear time approximation scheme for a generic problem about clustering of binary vectors subject to additional constraints.... (more)

A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees

This article presents a randomized (Las Vegas) distributed algorithm that constructs a minimum spanning tree (MST) in weighted networks with optimal... (more)

NEWS

About TALG

The ACM Transactions on Algorithms (TALG) publishes original research of the highest quality dealing with algorithms that are inherently discrete and finite, and having mathematical content in a natural way, either in the objective or in the analysis.

read more
Nearly ETH-Tight Algorithm for Planar Steiner Tree

The Planar Steiner Tree problem is one of the most fundamental NP-complete problems as it models many network design problems. Recall that an instance of this problem consists of a graph with edge weights, and a subset of vertices (often called terminals); the goal is to find a subtree of the graph of minimum total weight that connects all terminals. A seminal paper by Erickson et al. [Math. Oper. Res., 1987] considers instances where the underlying graph is planar and all terminals can be covered by the boundary of k faces. Erickson et al. show that the problem can be solved by an algorithm using n^O(k) time and n^O(k) space, where n denotes the number of vertices of the input graph. In the past 30 years there has been no significant improvement of this algorithm, despite several efforts. In this work, we give an algorithm for Planar Steiner Tree with running time 2^O(k) n^O(\sqrt{k}) using only polynomial space. Furthermore, we show that the running time of our algorithm is almost tight: we prove that there is no f(k) n^o(\sqrt{k}) algorithm for Planar Steiner Tree for any computable function f, unless the Exponential Time Hypothesis fails.

Ramsey Spanning Trees and their Applications

The \emph{metric Ramsey problem} asks for the largest subset $S$ of a metric space that can be embedded into an ultrametric (more generally into a Hilbert space) with a given distortion. Study of this problem was motivated as a non-linear version of Dvoretzky theorem. Mendel and Naor \cite{MN07} devised the so called Ramsey Partitions to address this problem, and showed the algorithmic applications of their techniques to approximate distance oracles and ranking problems. In this paper we study the natural extension of the metric Ramsey problem to graphs, and introduce the notion of \emph{Ramsey Spanning Trees}. We ask for the largest subset $S\subseteq V$ of a given graph $G=(V,E)$, such that there exists a spanning tree of $G$ that has small stretch for $S$. Applied iteratively, this provides a small collection of spanning trees, such that each vertex has a tree providing low stretch paths to {\em all other vertices}. The union of these trees serves as a special type of spanner, a {\em tree-padding spanner}. We use this spanner to devise the first compact stateless routing scheme with $O(1)$ routing decision time, and labels which are much shorter than in all currently existing schemes. We first revisit the metric Ramsey problem, and provide a new deterministic construction. We prove that for every $k$, any $n$-point metric space has a subset $S$ of size at least $n^{1-1/k}$ which embeds into an ultrametric with distortion $8k$. We use this result to obtain the state-of-the-art deterministic construction of a distance oracle. ....

All ACM Journals | See Full Journal Index

Search TALG
enter search term and/or author name