Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 13 Issue 3, May 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...