enter search term and/or author name
Faster and Simpler Sketches of Valuation Functions
Keren Cohavi, Shahar Dobzinski
Article No.: 30
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
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...
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
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
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
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
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...
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
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
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.)...
Thomas Dueholm Hansen, Haim Kaplan, Robert E. Tarjan, Uri Zwick
Article No.: 42
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
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...