ACM Transactions on

Algorithms (TALG)

Latest Articles

Faster Carry Bit Computation for Adder Circuits with Prescribed Arrival Times

We consider the fundamental problem of constructing fast circuits for the carry bit computation in binary addition. Up to a small additive constant,... (more)

Dynamic Beats Fixed: On Phase-based Algorithms for File Migration

We construct a deterministic 4-competitive algorithm for the online file migration problem, beating the currently best 20-year-old, 4.086-competitive Move-To-Local-Min (Mtlm) algorithm by Bartal et al. (SODA 1997). Like Mtlm, our algorithm also operates in phases, but it adapts their lengths dynamically depending on the geometry of... (more)

Faster Approximation Schemes for the Two-Dimensional Knapsack Problem

For geometric optimization problems we often understand the computational complexity on a rough scale, but not very well on a finer scale. One example... (more)

An Optimal O(nm) Algorithm for Enumerating All Walks Common to All Closed Edge-covering Walks of a Graph

In this article, we consider the following problem. Given a directed graph G, output all walks of G... (more)

Exponential Separations in the Energy Complexity of Leader Election

Energy is often the most constrained resource for battery-powered wireless devices, and most of the energy is often spent on transceiver usage (i.e.,... (more)

Recognizing Weak Embeddings of Graphs

We present an efficient algorithm for a problem in the interface between clustering and graph embeddings. An embedding ϕ : G → M of a graph G into a 2-manifold M maps the vertices in V(G) to distinct points and the edges in E(G) to interior-disjoint Jordan arcs between the corresponding vertices. In applications in clustering,... (more)

Heavy Hitters and the Structure of Local Privacy

We present a new locally differentially private algorithm for the heavy hitters problem that achieves optimal worst-case error as a function of all standardly considered parameters. Prior work obtained error rates that depend optimally on the number of users, the size of the domain, and the privacy parameter but depend sub-optimally on the failure... (more)

Spanning Circuits in Regular Matroids

We consider the fundamental Matroid Theory problem of finding a circuit in a matroid containing a set T of given terminal elements. For graphic matroids, this corresponds to the problem of finding a simple cycle passing through a set of given terminal edges in a graph. The algorithmic study of the problem on regular matroids, a superclass of... (more)

Ordered Level Planarity and Its Relationship to Geodesic Planarity, Bi-Monotonicity, and Variations of Level Planarity

We introduce and study the problem Ordered Level Planarity, which asks for a planar drawing of a... (more)

Improving TSP Tours Using Dynamic Programming over Tree Decompositions

Given a traveling salesman problem (TSP) tour H in graph G, a k-move is an operation that removes k edges from H and adds k edges of G so that a new... (more)

A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem

We present a factor &frac;43 approximation algorithm for the problem of finding a minimum 2-edge connected spanning subgraph of a given undirected... (more)


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

SODA'18 Editorial

Faster Replacement Paths and Distance Sensitivity Oracles

Given a directed n-node graph G with integer edge weights in [-M,M], 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 in G avoiding e. In this paper we achieve the following main results: 1) We describe an algorithm with runtime $\tilde{O}(Mn^{\omega})$ that computes the lengths of all the replacement paths for a given source-target pair (s,t). Here $\omega<2.373$ is fast matrix multiplication exponent. For a comparison, the previous fastest algorithms have runtime $\tilde{O}(Mn^{1+2\omega/3})$ [Weimann,Yuster-FOCS'10] and $\tilde{O}(n^{2.5})$ in the unweighted case [Roditty,Zwick-ICALP'05]. 2) We describe an algorithm with runtime $\tilde{O}(M^{\frac{1}{4-\omega}}n^{2+\frac{1}{4-\omega}})$ that computes the lengths of all the replacement paths for a given source s. Our runtime reduces to $\tilde{O}(Mn^\omega)$ for positive weights, hence matching our mentioned result for the simpler case where also the target t is fixed. 3) We present a data structure (a.k.a. distance sensitivity oracle) that answers to queries of the form (s,t,e) with the length of the associated replacement path. For a given parameter $\alpha\in [0,1]$, our oracle has preprocessing time $\tilde{O}(Mn^{\omega+\frac{1}{2}}+Mn^{\omega+\alpha(4-\omega)})$ and query time $\tilde{O}(n^{1-\alpha})$. In particular, we achieve for the first time simultaneously subcubic preprocessing time and sublinear query time. For a comparison, the previous best oracle has $\tilde{O}(Mn^{\omega+1-\alpha})$ preprocessing time and (superlinear) $\tilde{O}(n^{1+\alpha})$ query time [Weimann,Yuster-FOCS'10]. All the mentioned results are randomized: a wrong distance is output with polynomially small probability in n.

Randomized Memoryless Algorithms for the Weighted and the Generalized $k$-server Problems

The weighted $k$-server problem is a generalization of the $k$-server problem, wherein the cost of moving a server of weight $\beta_i$ through a distance $d$ is $\beta_i\cdot 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 paper, 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. We first prove that there is an $\alpha_k$-competitive memoryless algorithm for this problem, where $\alpha_k=\alpha_{k-1}^2+3\alpha_{k-1}+1$; $\alpha_1=1$. We complement this result by proving that no randomized memoryless algorithm can have a competitive ratio less than $\alpha_k$. Finally, we prove that the above bounds also hold for the generalized $k$-server problem on weighted uniform metrics.

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