Abstract: Marek Cygan, Fabrizio Grandoni, Danny Hermelin

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 depends solely on the parameter. Recent years have seen major advances in the study of both upper and lower bound techniques for kernelization, and by now this area has become one of the major research threads in parameterized complexity. In this article, we consider kernelization for problems on d-degenerate graphs, that is, graphs such that any subgraph contains a vertex of degree at most d. PubDate: Wed, 09 Aug 2017 00:00:00 GMT

Abstract: Thomas Dueholm Hansen, Haim Kaplan, Robert E. Tarjan, Uri Zwick

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(log n) amortized time on a heap of n items. Hollow heaps are the simplest structure to achieve these bounds. Hollow heaps combine two novel ideas: the use of lazy deletion and re-insertion to do decrease-key operations and the use of a dag (directed acyclic graph) instead of a tree or set of trees to represent a heap. PubDate: Thu, 27 Jul 2017 00:00:00 GMT

Abstract: Michael Dinitz, Guy Kortsarz, Zeev Nutov

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(&sqrt;n), O(&sqrt;k)} [Gupta et al. 2010]. In Gupta et al. [2010], it is also shown that ratio ρ for Steiner k-Forest implies ratio O(ρ · log 2n) for the related Dial-a-Ride problem. The only other algorithm known for Dial-a-Ride, besides the one resulting from Gupta et al. [2010], has ratio O(&sqrt;n) [Charikar and Raghavachari 1998]. PubDate: Thu, 13 Jul 2017 00:00:00 GMT

Abstract: Allan Borodin, Aadhar Jain, Hyun Chul Lee, Yuli Ye

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 distance between any pair, the goal is to select a subset S satisfying the following three criteria: (a) the subset S satisfies some constraint (e.g., bounded cardinality), (b) the subset contains results of high “quality,” and (c) the subset contains results that are “diverse” relative to the distance measure. The goal of result diversification is to produce a diversified subset while maintaining high quality as much as possible. PubDate: Thu, 13 Jul 2017 00:00:00 GMT

Abstract: Chidambaram Annamalai, Christos Kalaitzis, Ola Svensson

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 certain Configuration-LP can be used to estimate the value of the optimal allocation to within a factor of 4+ ϵ. In contrast, however, the best-known approximation algorithm for the problem has an unspecified large constant guarantee. In this article, we significantly narrow this gap by giving a 13-approximation algorithm for the problem. Our approach develops a local search technique introduced by Haxell [13] for hypergraph matchings and later used in this context by Asadpour, Feige, and Saberi [2]. PubDate: Fri, 26 May 2017 00:00:00 GMT

Abstract: Michael A. Bender, Martín Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, Seth Gilbert

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 be moved, this problem is called the memory allocation problem. The competitive ratio for this problem has matching upper and lower bounds that are logarithmic in the number of requests and in the ratio of the largest to smallest requests. This article defines the storage reallocation problem, where previously allocated blocks can be moved, or reallocated, but at some cost. This cost is determined by the allocation/reallocation cost function. PubDate: Fri, 26 May 2017 00:00:00 GMT

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 by current research, unlike similar minimization problems that have been widely studied. In this work, we identify a few submodular maximization problems for which one can get a better approximation for symmetric objectives than the state-of-the-art approximation for general submodular functions. We first consider the problem of maximizing a non-negative symmetric submodular function f:2N → R+ subject to a down-monotone solvable polytope P ⊆ [0, 1]N. For this problem, we describe an algorithm producing a fractional solution of value at least 0.432 ċ f(OPT), where OPT is the optimal integral solution. PubDate: Fri, 26 May 2017 00:00:00 GMT

Abstract: Archontia C. Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov, Saket Saurabh

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. showed that the special case when F contains at least one planar graph has a kernel of size f(F) ċ kg(F) for some functions f and g. They left open whether this Planar F-Minor-Free Deletion problem has kernels whose size is uniformly polynomial, of the form f(F) ċ kc for some universal constant c. PubDate: Mon, 20 Mar 2017 00:00:00 GMT

Abstract: Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh

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 an integer q, efficiently computes a q-representative family F′ of F of size approximately (p+q&atop;p). In this article, we consider the efficient computation of q-representative families for product families F. A family F is a product family if there exist families A and B such that F = { A, &cup, B : A ∈ A, B ∈ B, A, &cap, B = ∅}. PubDate: Mon, 13 Mar 2017 00:00:00 GMT

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 &vtilde;:2N→ R is an α-sketch of v if for every set S we have that v(S)/α ≤ &vtilde;(S) ≤ v(S) and &vtilde; can be described in poly(n) bits. Goemans et al. [SODA’09] showed that if v is submodular then there exists an õ(&sqrt;n)-sketch that can be constructed using polynomially many value queries (this is essentially the best possible, as Balcan and Harvey [STOC’11] show that no submodular function admits an n1/3 - ε-sketch). Based on their work, Balcan et al. PubDate: Mon, 06 Mar 2017 00:00:00 GMT

Abstract: Christian Glacet, Avery Miller, Andrzej Pelc

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 all nodes have to output the label of the elected leader. If the nodes of the network are anonymous, the task of leader election is formulated as follows: every node v of the network must output a simple path, which is coded as a sequence of port numbers, such that all these paths end at a common node, the leader. PubDate: Mon, 06 Mar 2017 00:00:00 GMT

Abstract: Anna C. Gilbert, Yi Li, Ely Porat, Martin J. Strauss

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 approximates x by &xwidehat; = R(Φ x), which must satisfy ‖ &xwidehat;-x‖1 ≤ (1+ε)‖ x - xk‖1. We consider the “for all” model, in which a single matrix Φ, possibly “constructed” non-explicitly using the probabilistic method, is used for all signals x. The best existing sublinear algorithm by Porat and Strauss [2012] uses O(ε−3klog (N/k)) measurements and runs in time O(k1 − αNα) for any constant α > 0. In this article, we improve the number of measurements to O(ε − 2klog (N/k)), matching the best existing upper bound (attained by super-linear algorithms), and the runtime to O(k1+βpoly(log N,1/ε)), with a modest restriction that k ⩽ N1 − α and ε ⩽ (log k/log N)γ for any constants α, β, γ ... PubDate: Mon, 06 Mar 2017 00:00:00 GMT

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 variables are set independently. We examine the distributions on these variables that arise during intermediate stages of MT. We show that these configurations have a more or less “random” form, building further on the MT-distribution concept of Haeupler et al. in understanding the (intermediate and) output distribution of MT. This has a variety of algorithmic applications; the most important is that bad events can be found relatively quickly, improving on MT across the complexity spectrum. PubDate: Mon, 06 Mar 2017 00:00:00 GMT

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 ∈ RN in time k1 + α(log N)O(1). Specifically, the algorithm is given query access to x and computes a k-sparse &xtilde; ∈ RN satisfying ‖ &xtilde;− &xhat;‖1 ≤ c ‖ &xhat;− Hk(&xhat)‖‖1 for an absolute constant c > 0, where &xhat; is the transform of x and Hk(&xhat) is its best k-sparse approximation. Our algorithm is fully deterministic and only uses nonadaptive queries to x (i.e., all queries are determined and performed in parallel when the algorithm starts). PubDate: Mon, 06 Mar 2017 00:00:00 GMT