Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG) - Special Issue on SODA'15 and Regular Papers, Volume 13 Issue 2, May 2017

Section: Special Issue on SODA'15

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 FC, 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(nlog 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...