Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG) - Special Issue on SODA’16 and Regular Papers, Volume 14 Issue 3, July 2018

Section: Special Issue on SODA’16

Editorial: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016 Special Issue
Arnab Bhattacharyya, Fabrizio Grandoni, Aleksandar Nikolov, Barna Saha, Saket Saurabh, Aravindan Vijayaraghavan, Qin Zhang
Article No.: 26
DOI: 10.1145/3230647

Subtree Isomorphism Revisited
Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Or Zamir
Article No.: 27
DOI: 10.1145/3093239

The Subtree Isomorphism problem asks whether a given tree is contained in another given tree. The problem is of fundamental importance and has been studied since the 1960s. For some variants, e.g., ordered trees, near-linear time...

On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique
Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, Tselil Schramm
Article No.: 28
DOI: 10.1145/3178538

The problem of finding large cliques in random graphs and its “planted” variant, where one wants to recover a clique of size ω ≫ log (n) added to an Erdős-Rényi graph G...

CoveringLSH: Locality-Sensitive Hashing without False Negatives
Rasmus Pagh
Article No.: 29
DOI: 10.1145/3155300

We consider a new construction of locality-sensitive hash functions for Hamming space that is covering in the sense that is it guaranteed to produce a collision for every pair of vectors within a given radius r. The construction is...

Improved Deterministic Algorithms for Linear Programming in Low Dimensions
Timothy M. CHAN
Article No.: 30
DOI: 10.1145/3155312

Chazelle and Matoušek [J. Algorithms, 1996] presented a derandomization of Clarkson’s sampling-based algorithm [J. ACM, 1995] for solving linear programs with n constraints and d variables in...

A Faster Subquadratic Algorithm for Finding Outlier Correlations
Matti Karppa, Petteri Kaski, Jukka Kohonen
Article No.: 31
DOI: 10.1145/3174804

We study the problem of detecting outlier pairs of strongly correlated variables among a collection of n variables with otherwise weak pairwise correlations. After normalization, this task amounts to the geometric task where we are...

Deterministic Algorithms for Submodular Maximization Problems
Niv Buchbinder, Moran Feldman
Article No.: 32
DOI: 10.1145/3184990

Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function maximization. In this area, most algorithms are randomized, and in...

Near-Optimal Light Spanners
Shiri Chechik, Christian Wulff-Nilsen
Article No.: 33
DOI: 10.1145/3199607

A spanner H of a weighted undirected graph G is a “sparse” subgraph that approximately preserves distances between every pair of vertices in G. We refer to H as a δ-spanner of G for some...

Section: Regular Papers

Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, MichaŁ Pilipczuk, Marcin Wrochna
Article No.: 34
DOI: 10.1145/3186898

We investigate the complexity of several fundamental polynomial-time solvable problems on graphs and on matrices, when the given instance has low treewidth; in the case of matrices, we consider the treewidth of the graph formed by non-zero...

Subexponential Parameterized Algorithm for Interval Completion
Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, MichaŁ Pilipczuk
Article No.: 35
DOI: 10.1145/3186896

In the Interval Completion problem we are given an n-vertex graph G and an integer k, and the task is to transform G by making use of at most k edge additions into an interval graph. This is...

Faster Algorithms for Computing Plurality Points
Mark De Berg, Joachim Gudmundsson, Mehran Mehr
Article No.: 36
DOI: 10.1145/3186990

Let V be a set of n points in Rd, which we call voters. A point p ∈ Rd is preferred over another point p′ ∈ Rd by a voter υ ∈ V if...

Erratum: Approximating Minimum-Cost Connectivity Problems via Uncrossable Bifamilies
Zeev Nutov
Article No.: 37
DOI: 10.1145/3186991

There are two errors in our article “Approximating Minimum-Cost Connectivity Problems via Uncrossable Bifamilies” (ACM Transactions on Algorithms (TALG), 9(1), Article No. 1, 2012). In that article, we consider the...

Exploring the Complexity of Layout Parameters in Tournaments and Semicomplete Digraphs
Florian Barbero, Christophe Paul, MichaŁ Pilipczuk
Article No.: 38
DOI: 10.1145/3196276

A simple digraph is semicomplete if for any two of its vertices u and v, at least one of the arcs (u,v) and (v,u) is present. We study the complexity of computing two layout parameters of...

Data Structures for Weighted Matching and Extensions to b-matching and f-factors
Harold N. Gabow
Article No.: 39
DOI: 10.1145/3183369

This article shows the weighted matching problem on general graphs can be solved in time O(n(m + n log n)) for n and m the number of vertices and edges, respectively. This was previously known only...