Search ACM DL

Search Issue

enter search term and/or author name

Section:

**Editorial**

Alexandr Andoni, Debmalya Panigrahi, Marcin Pilipczuk

Article No.: 18

DOI: 10.1145/3038922

**Tight Bounds on Vertex Connectivity Under Sampling**

Keren Censor-Hillel, Mohsen Ghaffari, George Giakkoupis, Bernhard Haeupler, Fabian Kuhn

Article No.: 19

DOI: 10.1145/3086465

A fundamental result by Karger [10] 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

DOI: 10.1145/3039241

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

**Dynamic Facility Location via Exponential Clocks**

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

Article No.: 21

DOI: 10.1145/2928272

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

Shi Li

Article No.: 22

DOI: 10.1145/2983633

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

DOI: 10.1145/2981561

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

DOI: 10.1145/3009909

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

DOI: 10.1145/3011870

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

DOI: 10.1145/3039873

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

DOI: 10.1145/3039242

We present an algorithm for surface reconstruction from a point cloud. It runs in *O*(*n*log *n*) time, where *n* is the number of sample points, and this is optimal in the pointer machine model. The only existing...

**Asymptotically Optimal Encodings of Range Data Structures for Selection and Top- k Queries**

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

Article No.: 28

DOI: 10.1145/3012939

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

DOI: 10.1145/3014587

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