Search ACM DL

Search Issue

enter search term and/or author name

**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 *n*^{k/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...