Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG) - Special Issue on SODA'12 and Regular Papers, Volume 12 Issue 1, February 2016

Section: Special Issue on SODA'12

Editorial to the Special Issue on SODA'12
Yuval Rabani, Andrea Richa, Jared Saia, David P. Woodruff
Article No.: 1
DOI: 10.1145/2846001

Approximation Algorithms and Hardness of the k-Route Cut Problem
Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou
Article No.: 2
DOI: 10.1145/2644814

We study the k-route cut problem: given an undirected edge-weighted graph G = (V, E), a collection {(s1, t1), (s2, t2), …,...

Computing the Distance between Piecewise-Linear Bivariate Functions
Guillaume Moroz, Boris Aronov
Article No.: 3
DOI: 10.1145/2847257

We consider the problem of computing the distance between two piecewise-linear bivariate functions f and g defined over a common domain M, induced by the L2 norm—that is, ‖ f...

Fast Zeta Transforms for Lattices with Few Irreducibles
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof, Pekka Parviainen
Article No.: 4
DOI: 10.1145/2629429

We investigate fast algorithms for changing between the standard basis and an orthogonal basis of idempotents for Möbius algebras of finite lattices. We show that every lattice with v elements, n of which are nonzero and...

Width of Points in the Streaming Model
Alexandr Andoni, Huy L. Nguyêݱn
Article No.: 5
DOI: 10.1145/2847259

In this article, we show how to compute the width of a dynamic set of low-dimensional points in the streaming model. In particular, we assume that the stream contains both insertions of points and deletions of points to a set S, and the...

Bypassing UGC from Some Optimal Geometric Inapproximability Results
Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu
Article No.: 6
DOI: 10.1145/2737729

The Unique Games Conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective...

Section: Special Issue on SODA'12

Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
Ofer Neiman, Shay Solomon
Article No.: 7
DOI: 10.1145/2700206

A maximal matching can be maintained in fully dynamic (supporting both addition and deletion of edges) n-vertex graphs using a trivial deterministic algorithm with a worst-case update time of O(n). No deterministic algorithm...

On the k-Independence Required by Linear Probing and Minwise Independence
Mihai Pǎtraşcu, Mikkel Thorup
Article No.: 8
DOI: 10.1145/2716317

We show that linear probing requires 5-independent hash functions for expected constant-time performance, matching an upper bound of Pagh et al. [2009]. More precisely, we construct a random 4-independent hash function yielding expected...

Sparse Sums of Positive Semidefinite Matrices
Marcel K. De Carli Silva, Nicholas J. A. Harvey, Cristiane M. Sato
Article No.: 9
DOI: 10.1145/2746241

Many fast graph algorithms begin by preprocessing the graph to improve its sparsity. A common form of this is spectral sparsification, which involves removing and reweighting the edges of the graph while approximately preserving its spectral...

Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets
Anupam Gupta, Viswanath Nagarajan, R. Ravi
Article No.: 10
DOI: 10.1145/2746226

Consider the following problem: given a set system (U, Ω) and an edge-weighted graph G = (U, E) on the same universe U, find the set A ∈ Ω such that the Steiner tree cost with...

Dominator Tree Certification and Divergent Spanning Trees
Loukas Georgiadis, Robert E. Tarjan
Article No.: 11
DOI: 10.1145/2764913

How does one verify that the output of a complicated program is correct? One can formally prove that the program is correct, but this may be beyond the power of existing methods. Alternatively, one can check that the output produced for a...

Approximating the Diameter of Planar Graphs in Near Linear Time
Oren Weimann, Raphael Yuster
Article No.: 12
DOI: 10.1145/2764910

We present a (1 + ϵ)-approximation algorithm running in O(f(ϵ) · nlog 4n) time for finding the diameter of an undirected planar graph with n vertices and with nonnegative edge...