Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 12 Issue 2, February 2016

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation
Lukáš Poláček, Ola Svensson
Article No.: 13
DOI: 10.1145/2818695

The restricted max-min fair allocation problem (also known as the restricted Santa Claus problem) is one of few problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, Asadpour et...

A New Approach to Incremental Cycle Detection and Related Problems
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Robert E. Tarjan
Article No.: 14
DOI: 10.1145/2756553

We consider the problem of detecting a cycle in a directed graph that grows by arc insertions and the related problems of maintaining a topological order and the strong components of such a graph. For these problems, we give two algorithms, one...

Anarchy Is Free in Network Creation
Ronald Graham, Linus Hamilton, Ariel Levavi, Po-Shen Loh
Article No.: 15
DOI: 10.1145/2729978

The Internet has emerged as perhaps the most important network in modern computing, but rather miraculously, it was created through the individual actions of a multitude of agents rather than by a central planning authority. This motivates the...

Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems
Thomas Bläsius, Ignaz Rutter
Article No.: 16
DOI: 10.1145/2738054

In this article, we define and study the new problem of Simultaneous PQ-Ordering. Its input consists of a set of PQ-trees, which represent sets of circular orders of their leaves, together with a set of child-parent relations...

Faster Spectral Sparsification and Numerical Algorithms for SDD Matrices
Ioannis Koutis, Alex Levin, Richard Peng
Article No.: 17
DOI: 10.1145/2743021

We study algorithms for spectral graph sparsification. The input is a graph G with n vertices and m edges, and the output is a sparse graph &Gtilde; that approximates G in an algebraic sense. Concretely, for all...

Optimal Partitioning for Dual-Pivot Quicksort
Martin Aumüller, Martin Dietzfelbinger
Article No.: 18
DOI: 10.1145/2743020

Dual-pivot quicksort refers to variants of classical quicksort where in the partitioning step two pivots are used to split the input into three segments. This can be done in different ways, giving rise to different algorithms. Recently, a...

Sorting and Selection with Imprecise Comparisons
Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson
Article No.: 19
DOI: 10.1145/2701427

We consider a simple model of imprecise comparisons: there exists some δ > 0 such that when a subject is given two elements to compare, if the values of those elements (as perceived by the subject) differ by at least δ, then the...

Improved Approximation Algorithms for Relay Placement
Alon Efrat, Sándor P. Fekete, Joseph S. B. Mitchell, Valentin Polishchuk, Jukka Suomela
Article No.: 20
DOI: 10.1145/2814938

In the relay placement problem, the input is a set of sensors and a number r ⩾ 1, the communication range of a relay. In the one-tier version of the problem, the objective is to place a minimum number of relays so that between...

Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, Somnath Sikdar
Article No.: 21
DOI: 10.1145/2797140

We present a linear-time algorithm to compute a decomposition scheme for graphs G that have a set XV(G), called a treewidth-modulator, such that the treewidth of GX is bounded by a...

Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension
Ittai Abraham, Shiri Chechik, Cyril Gavoille, David Peleg
Article No.: 22
DOI: 10.1145/2818694

This article proposes a forbidden-set labeling scheme for the family of unweighted graphs with doubling dimension bounded by α. For an n-vertex graph G in this family, and for any desired precision parameter ε > 0, the...

A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2
Guy Kortsarz, Zeev Nutov
Article No.: 23
DOI: 10.1145/2786981

The Tree Augmentation Problem (TAP) is as follows: given a connected graph G=(V, ϵ) and an edge set E on V, find a minimum size subset of edges FE such that (V,...

The Minset-Poset Approach to Representations of Graph Connectivity
Harold N. Gabow
Article No.: 24
DOI: 10.1145/2764909

Various instances of the minimal-set poset (minset-poset for short) have been proposed in the literature, e.g., the representation of Picard and Queyranne for all st-minimum cuts of a flow network. We begin with an explanation of why this...

Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner
Michael Dinitz, Guy Kortsarz, Ran Raz
Article No.: 25
DOI: 10.1145/2818375

We study the well-known Label Cover problem under the additional requirement that problem instances have large girth. We show that if the girth is some k, the problem is roughly 2log 1-ε n)/k hard to...

Segmentation of Trajectories on Nonmonotone Criteria
Boris Aronov, Anne Driemel, Marc Van Kreveld, Maarten Löffler, Frank Staals
Article No.: 26
DOI: 10.1145/2660772

In the trajectory segmentation problem, we are given a polygonal trajectory with n vertices that we have to subdivide into a minimum number of disjoint segments (subtrajectories) that all satisfy a given criterion. The problem is known to...