Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 13 Issue 4, December 2017

Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets
Serge Gaspers, Gregory B. Sorkin
Article No.: 44
DOI: 10.1145/3111499

We show a method resulting in the improvement of several polynomial-space, exponential-time algorithms. The method capitalizes on the existence of small balanced separators for sparse graphs, which can be exploited for branching to disconnect an...

A Data Structure for Nearest Common Ancestors with Linking
Harold N. Gabow
Article No.: 45
DOI: 10.1145/3108240

Consider a forest that evolves via link operations that make the root of one tree the child of a node in another tree. Intermixed with link operations are nca operations, which return the nearest common ancestor of two given...

Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts
M. S. Ramanujan, Saket Saurabh
Article No.: 46
DOI: 10.1145/3128600

A skew-symmetric graph (D=(V,A),σ) is a directed graph D with an involution σ on the set of vertices and arcs. Flows on skew-symmetric graphs have been used to generalize maximum flow and maximum...

Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications
Hsien-Kuei Hwang, Svante Janson, Tsung-Hsi Tsai
Article No.: 47
DOI: 10.1145/3127585

Divide-and-conquer recurrences of the form f(n) = f (⌊ &fracn2;⌋ ) + f ( ⌈ &fracn2;⌉ ) + g(n) (n⩾ 2), with g(n) and...

Counting Thin Subgraphs via Packings Faster than Meet-in-the-Middle Time
Andreas Björklund, Petteri Kaski, Łukasz Kowalik
Article No.: 48
DOI: 10.1145/3125500

Vassilevska and Williams (STOC’09) showed how to count simple paths on k vertices and matchings on k/2 edges in an n-vertex graph in time nk/2+O(1). In the same year, two different...

Spider Covers for Prize-Collecting Network Activation Problem
Takuro Fukunaga
Article No.: 49
DOI: 10.1145/3132742

In the network activation problem, each edge in a graph is associated with an activation function that decides whether the edge is activated from weights assigned to its end nodes. The feasible solutions of the problem are node weights such that...

Distributed Private Data Analysis: Lower Bounds and Practical Constructions
Elaine Shi, T.-H. Hubert Chan, Eleanor Rieffel, Dawn Song
Article No.: 50
DOI: 10.1145/3146549

We consider a distributed private data analysis setting, where multiple parties each hold some sensitive data and they wish to run a protocol to learn some aggregate statistics over the distributed dataset, while protecting each user’s...

Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai
Article No.: 51
DOI: 10.1145/3146550

We study the problem of maintaining a breadth-first spanning tree (BFS tree) in partially dynamic distributed networks modeling a sequence of either failures or additions of communication links (but not both). We present...

Approximation Algorithms for Computing Maximin Share Allocations
Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, Amin Saberi
Article No.: 52
DOI: 10.1145/3147173

We study the problem of computing maximin share allocations, a recently introduced fairness notion. Given a set of n agents and a set of goods, the maximin share of an agent is the best she can guarantee to herself, if she is allowed to...

Parallel Algorithms and Concentration Bounds for the Lovász Local Lemma via Witness DAGs
Bernhard Haeupler, David G. Harris
Article No.: 53
DOI: 10.1145/3147211

The Lovász Local Lemma (LLL) is a cornerstone principle in the probabilistic method of combinatorics, and a seminal algorithm of Moser and Tardos (2010) provides an efficient randomized algorithm to implement it. This can be parallelized...

Maximizing Polynomials Subject to Assignment Constraints
Konstantin Makarychev, Maxim Sviridenko
Article No.: 54
DOI: 10.1145/3147137

We study the q-adic assignment problem. We first give an O(n(q−1)/2))-approximation algorithm for the Koopmans--Beckman version of the problem, improving upon the result of Barvinok. Then, we introduce a new...

Toward Optimal Self-Adjusting Heaps
Amr Elmasry
Article No.: 55
DOI: 10.1145/3147138

We give a variant of the pairing heaps that achieves the following amortized costs: O(1) per find-min and insert, O(log log n) per decrease-key and meld, O(log n) per...