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
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
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
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
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
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
Article No.: 49
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
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
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
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
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
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...
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...