enter search term and/or author name
Tight Bounds on Vertex Connectivity Under Sampling
Keren Censor-Hillel, Mohsen Ghaffari, George Giakkoupis, Bernhard Haeupler, Fabian Kuhn
Article No.: 19
A fundamental result by Karger  states that for any λ-edge-connected graph with n nodes, independently sampling each edge with probability p = Ω(log (n)/λ) results in a graph that has edge...
Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties
Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, C. Seshadhri
Article No.: 20
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...
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...
On Uniform Capacitated k-Median Beyond the Natural LP Relaxation
Article No.: 22
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...
An Improved Approximation for k-Median and Positive Correlation in Budgeted Optimization
Jarosław Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, Khoa Trinh
Article No.: 23
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...
Section: Special Issue on SODA'15
Generating Random Permutations by Coin Tossing: Classical Algorithms, New Analysis, and Modern Implementation
Axel Bacher, Olivier Bodini, Hsien-Kuei Hwang, Tsung-Hsi Tsai
Article No.: 24
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...
Smoothed Analysis of Local Search for the Maximum-Cut Problem
Michael Etscheid, Heiko Röglin
Article No.: 25
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...
Submatrix Maximum Queries in Monge Matrices and Partial Monge Matrices, and Their Applications
Haim Kaplan, Shay Mozes, Yahav Nussbaum, Micha Sharir
Article No.: 26
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...
A Fast and Simple Surface Reconstruction Algorithm
Siu-Wing Cheng, Jiongxin Jin, Man-Kit Lau
Article No.: 27
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...
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...
Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
Robert Ganian, M. S. Ramanujan, Stefan Szeider
Article No.: 29
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...