Search ACM DL

Search Issue

enter search term and/or author name

**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*:2^{N}→ 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*-M*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 *A* ∈ *F* and *B* of size *q* such that *A*∩*B* = ∅ 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...