ACM Transactions on Algorithms

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 v˜:2^N→ R is an α-sketch of v if for every set S we have that v(S)/α ≤ v˜(S) ≤ v(S) and v˜ can be described in poly(n) ...

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 means that ...

An approximate sparse recovery system in ℓ₁ norm consists of parameters k, ϵ, N; an m-by-N measurement Φ; and a recovery algorithm R. Given a vector, x, the system approximates x by xˆ = R(Φ x), which must satisfy ‖ xˆ-x‖₁ ≤ (1+ϵ)‖ x - x_k‖₁. We consider ...

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 initial stage of MT, the ...

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 ∈ R^N in time k^{1 + α}(log N)^O(1). Specifically, the algorithm ...

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 resulting graph does not contain any member of F as a minor. At FOCS 2012, Fomin et al. ...

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 A′ ∈ F′ such that A′ ∩ B = ∅. Recently, we provided an algorithm that, for a given family F of sets of size p together with ...

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 ...

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 cannot ...

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 attention ...

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 pairs. The best known ratio for this problem is min {O(√n), O(√...

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.) with a ...

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 as amortized; delete and delete-min take O(...

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 whose size ...