Even though local search heuristics are the method of choice in practice for many well-studied optimization problems, most of them behave poorly in the worst case. This is, in particular, the case for the Maximum-Cut Problem, for which local search can take an exponential number of steps to terminate and the problem of computing a local optimum is PLS-complete. To narrow the gap between theory and practice, we study local search for the Maximum-Cut Problem in the framework of smoothed analysis in which inputs are subject to a small amount of random noise. We show that the smoothed number of iterations is quasi-polynomial, that is, it is bounded from above by a polynomial in nlog n and φ, where n denotes the number of nodes and φ denotes the perturbation parameter. PubDate: Tue, 21 Mar 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

Abstract: Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, C. Seshadhri

The primary problem in property testing is to decide whether a given function satisfies a certain property or is far from any function satisfying it. This crucially requires a notion of distance between functions. The most prevalent notion is the Hamming distance over the uniform distribution on the domain. This restriction to uniformity is rather limiting, and it is important to investigate distances induced by more general distributions. In this article, we provide simple and optimal testers for bounded derivative properties over arbitrary product distributions. Bounded derivative properties include fundamental properties, such as monotonicity and Lipschitz continuity. Our results subsume almost all known results (upper and lower bounds) on monotonicity and Lipschitz testing over arbitrary ranges. PubDate: Fri, 10 Mar 2017 00:00:00 GMT

Abstract: Siu-Wing Cheng, Jiongxin Jin, Man-Kit Lau

We present an algorithm for surface reconstruction from a point cloud. It runs in O(nlog n) time, where n is the number of sample points, and this is optimal in the pointer machine model. The only existing O(nlog n)-time algorithm is due to Funke and Ramos, and it uses some sophisticated data structures. The key task is to extract a locally uniform subsample from the input points. Our algorithm is much simpler and it is based on a variant of the standard octree. We built a prototype that runs an implementation of our algorithm to extract a locally uniform subsample, invokes Cocone to reconstruct a surface from the subsample, and adds back the sample points absent from the subsample via edge flips. PubDate: Fri, 10 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

Dependent rounding is a useful technique for optimization problems with hard budget constraints. This framework naturally leads to negative correlation properties. However, what if an application naturally calls for dependent rounding on the one hand and desires positive correlation on the other? More generally, we develop algorithms that guarantee the known properties of dependent rounding but also have nearly bestpossible behavior—near-independence, which generalizes positive correlation—on “small” subsets of the variables. The recent breakthrough of Li and Svensson for the classical k-median problem has to handle positive correlation in certain dependent rounding settings, and does so implicitly. We improve upon Li-Svensson’s approximation ratio for k-median from 2.732 + ε to 2.675 + ε by developing an algorithm that improves upon various aspects of their work. PubDate: Mon, 06 Mar 2017 00:00:00 GMT

We describe a data structure for submatrix maximum queries in Monge matrices or partial Monge matrices, where a query seeks the maximum element in a contiguous submatrix of the given matrix. The structure, for an n × n Monge matrix, takes O(nlog n) space and O(nlogn) preprocessing time, and answers queries in O(log2n) time. For partial Monge matrices, the space grows by α(n), the preprocessing grows by α(n)logn (α(n) is the inverse Ackermann function), and the query remains O(log2n). Our design exploits an interpretation of the column maxima in a Monge (partial Monge, respectively) matrix as an upper envelope of pseudo-lines (pseudo-segments, respectively). PubDate: Mon, 06 Mar 2017 00:00:00 GMT

Abstract: Roberto Grossi, John Iacono, Gonzalo Navarro, Rajeev Raman, S. Rao Satti

Given an array A[1, n] of elements with a total order, we consider the problem of building a data structure that solves two queries: (a) selection queries receive a range [i, j] and an integer k and return the position of the kth largest element in A[i, j]; (b) top-k queries receive [i, j] and k and return the positions of the k largest elements in A[i, j]. These problems can be solved in optimal time, O(1+lg k/lg lg n) and O(k), respectively, using linear-space data structures. We provide the first study of the encoding data structures for the above problems, where A cannot be accessed at query time. PubDate: Mon, 06 Mar 2017 00:00:00 GMT

Abstract: Robert Ganian, M. S. Ramanujan, Stefan Szeider

The Constraint Satisfaction Problem (CSP) is a central and generic computational problem which provides a common framework for many theoretical and practical applications. A central line of research is concerned with the identification of classes of instances for which CSP can be solved in polynomial time; such classes are often called “islands of tractability.” A prominent way of defining islands of tractability for CSP is to restrict the relations that may occur in the constraints to a fixed set, called a constraint language, whereas a constraint language is conservative if it contains all unary relations. Schaefer’s famous Dichotomy Theorem (STOC 1978) identifies all islands of tractability in terms of tractable constraint languages over a Boolean domain of values. PubDate: Mon, 06 Mar 2017 00:00:00 GMT

Abstract: Hyung-Chan An, Ashkan Norouzi-Fard, Ola Svensson

The dynamic facility location problem is a generalization of the classic facility location problem proposed by Eisenstat, Mathieu, and Schabanel to model the dynamics of evolving social/infrastructure networks. The generalization lies in that the distance metric between clients and facilities changes over time. This leads to a trade-off between optimizing the classic objective function and the “stability” of the solution: There is a switching cost charged every time a client changes the facility to which it is connected. While the standard linear program (LP) relaxation for the classic problem naturally extends to this problem, traditional LP-rounding techniques do not, as they are often sensitive to small changes in the metric resulting in frequent switches. PubDate: Tue, 07 Feb 2017 00:00:00 GMT

Abstract: Axel Bacher, Olivier Bodini, Hsien-Kuei Hwang, Tsung-Hsi Tsai

Several simple, classical, little-known algorithms in the statistics and computer science literature for generating random permutations by coin tossing are examined, analyzed, and implemented. These algorithms are either asymptotically optimal or close to being so in terms of the expected number of times the random bits are generated. In addition to asymptotic approximations to the expected complexity, we also clarify the corresponding variances, as well as the asymptotic distributions. A brief comparative discussion with numerical computations in a multicore system is also given. PubDate: Tue, 07 Feb 2017 00:00:00 GMT

In this article, we study the uniform capacitated k-median (CKM) problem. In the problem, we are given a set F of potential facility locations, a set C of clients, a metric d over F ∪ C, an upper bound k on the number of facilities that we can open, and an upper bound u on the number of clients that each facility can serve. We need to open a subset S ⊆ F of k facilities and connect clients in C to facilities in S so that each facility is connected by at most u clients. The goal is to minimize the total connection cost over all clients. PubDate: Sat, 14 Jan 2017 00:00:00 GMT