Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 13 Issue 3, August 2017

Faster and Simpler Sketches of Valuation Functions
Keren Cohavi, Shahar Dobzinski
Article No.: 30
DOI: 10.1145/3039871

We present fast algorithms for sketching valuation functions. Let N (|N| = n) be some ground set and v:2N→ R be a function. We say that...

Time vs. Information Tradeoffs for Leader Election in Anonymous Trees
Christian Glacet, Avery Miller, Andrzej Pelc
Article No.: 31
DOI: 10.1145/3039870

Leader election is one of the fundamental problems in distributed computing. It calls for all nodes of a network to agree on a single node, called the leader. If the nodes of the network have distinct labels, then agreeing on a single node...

For-All Sparse Recovery in Near-Optimal Time
Anna C. Gilbert, Yi Li, Ely Porat, Martin J. Strauss
Article No.: 32
DOI: 10.1145/3039872

An approximate sparse recovery system in ℓ1 norm consists of parameters k, ε, N; an m-by-N measurement Φ; and a recovery algorithm R. Given a vector, x, the system...

Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution
David G. Harris, Aravind Srinivasan
Article No.: 33
DOI: 10.1145/3039869

Moser and Tardos have developed a powerful algorithmic approach (henceforth MT) to the Lovász Local Lemma (LLL); the basic operation done in MT and its variants is a search for “bad” events in a current configuration. In the...

Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform
Mahdi Cheraghchi, Piotr Indyk
Article No.: 34
DOI: 10.1145/3029050

For every fixed constant α > 0, we design an algorithm for computing the k-sparse Walsh-Hadamard transform (i.e., Discrete Fourier Transform over the Boolean cube) of an N-dimensional vector x...

Uniform Kernelization Complexity of Hitting Forbidden Minors
Archontia C. Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov, Saket Saurabh
Article No.: 35
DOI: 10.1145/3029051

The F-Minor-Free Deletion problem asks, for a fixed set F and an input consisting of a graph G and integer k, whether k vertices can be removed from G such that the...

Representative Families of Product Families
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh
Article No.: 36
DOI: 10.1145/3039243

A subfamily F′ of a set family F is said to q-represent F if for every AF and B of size q such that AB = ∅ there exists a set...

Combinatorial Algorithm for Restricted Max-Min Fair Allocation
Chidambaram Annamalai, Christos Kalaitzis, Ola Svensson
Article No.: 37
DOI: 10.1145/3070694

We study the basic allocation problem of assigning resources to players to maximize fairness. This is one of the few natural problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, a...

Cost-Oblivious Storage Reallocation
Michael A. Bender, Martín Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, Seth Gilbert
Article No.: 38
DOI: 10.1145/3070693

Databases allocate and free blocks of storage on disk. Freed blocks introduce holes where no data is stored. Allocation systems attempt to reuse such deallocated regions in order to minimize the footprint on disk. When previously allocated blocks...

Maximizing Symmetric Submodular Functions
Moran Feldman
Article No.: 39
DOI: 10.1145/3070685

Symmetric submodular functions are an important family of submodular functions capturing many interesting cases, including cut functions of graphs and hypergraphs. Maximization of such functions subject to various constraints receives little...

Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights
Michael Dinitz, Guy Kortsarz, Zeev Nutov
Article No.: 40
DOI: 10.1145/3077581

In the Steiner k-Forest problem, we are given an edge weighted graph, a collection D of node pairs, and an integer k ⩽ |D|. The goal is to find a min-weight subgraph that connects at least k...

Max-Sum Diversification, Monotone Submodular Functions, and Dynamic Updates
Allan Borodin, Aadhar Jain, Hyun Chul Lee, Yuli Ye
Article No.: 41
DOI: 10.1145/3086464

Result diversification is an important aspect in web-based search, document summarization, facility location, portfolio management, and other applications. Given a set of ranked results for a set of objects (e.g., web documents, facilities, etc.)...

Hollow Heaps
Thomas Dueholm Hansen, Haim Kaplan, Robert E. Tarjan, Uri Zwick
Article No.: 42
DOI: 10.1145/3093240

We introduce the hollow heap, a very simple data structure with the same amortized efficiency as the classical Fibonacci heap. All heap operations except delete and delete-min take O(1) time, worst case as well...

Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
Marek Cygan, Fabrizio Grandoni, Danny Hermelin
Article No.: 43
DOI: 10.1145/3108239

Kernelization is a strong and widely applied technique in parameterized complexity. In a nutshell, a kernelization algorithm for a parameterized problem transforms in polynomial time a given instance of the problem into an equivalent instance...