Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 12 Issue 3, June 2016

Scale-Free Compact Routing Schemes in Networks of Low Doubling Dimension
Goran Konjevod, Andréa W. Richa, Donglin Xia
Article No.: 27
DOI: 10.1145/2876055

We consider compact routing schemes in networks of low doubling dimension, where the doubling dimension is the least value α such that any ball in the network can be covered by at most 2α balls of half radius. There are two...

Distributed Algorithms for End-to-End Packet Scheduling in Wireless Ad Hoc Networks
V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan
Article No.: 28
DOI: 10.1145/2812811

Packet scheduling is a particular challenge in wireless networks due to interference from nearby transmissions. A distance-2 interference model serves as a useful abstraction here, and we study packet routing and scheduling under this model...

Fast Constructions of Lightweight Spanners for General Graphs
Michael Elkin, Shay Solomon
Article No.: 29
DOI: 10.1145/2836167

It is long known that for every weighted undirected n-vertex m-edge graph G = (V, E, ω), and every integer k ⩾ 1, there exists a ((2k − 1) · (1 +...

The Two-Edge Connectivity Survivable-Network Design Problem in Planar Graphs
Glencora Borradaile, Philip Klein
Article No.: 30
DOI: 10.1145/2831235

Consider the following problem: given a graph with edge costs and a subset Q of vertices, find a minimum-cost subgraph in which there are two edge-disjoint paths connecting every pair of vertices in Q. The problem is a...

LIMITS and Applications of Group Algebras for Parameterized Problems
Ioannis Koutis, Ryan Williams
Article No.: 31
DOI: 10.1145/2885499

The fastest known randomized algorithms for several parameterized problems use reductions to the k-MlD problem: detection of multilinear monomials of degree k in polynomials presented as circuits. The fastest known...

Approximating Semi-matchings in Streaming and in Two-Party Communication
Christian Konrad, Adi Rosén
Article No.: 32
DOI: 10.1145/2898960

We study the streaming complexity and communication complexity of approximating unweighted semi-matchings. A semi-matching in a bipartite graph G = (A, B, E) with n = |A| is a...

Optimal Orthogonal Graph Drawing with Convex Bend Costs
Thomas Bläsius, Ignaz Rutter, Dorothea Wagner
Article No.: 33
DOI: 10.1145/2838736

Traditionally, the quality of orthogonal planar drawings is quantified by the total number of bends or the maximum number of bends per edge. However, this neglects that, in typical applications, edges have varying importance. We consider the...

A Simple and Efficient Algorithm for Computing Market Equilibria
Lisa Fleischer, Rahul Garg, Sanjiv Kapoor, Rohit Khandekar, Amin Saberi
Article No.: 34
DOI: 10.1145/2905372

We give a new mathematical formulation of market equilibria in exchange economies using an indirect utility function: the function of prices and income that gives the maximum utility achievable. The formulation is a convex program...

Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Article No.: 35
DOI: 10.1145/2847419

Assume that a group of n people is going to an excursion and our task is to seat them into buses with several constraints each saying that a pair of people does not want to see each other in the same bus. This is a well-known graph coloring...

A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median
Mohammadtaghi Hajiaghayi, Wei Hu, Jian Li, Shi Li, Barna Saha
Article No.: 36
DOI: 10.1145/2854153

In this article, we consider the fault-tolerant k-median problem and give the first constant factor approximation algorithm for it. In the fault-tolerant generalization of the classical k-median problem, each client j...

On the Expected Complexity of Voronoi Diagrams on Terrains
Anne Driemel, Sariel Har-Peled, Benjamin Raichel
Article No.: 37
DOI: 10.1145/2846099

We investigate the combinatorial complexity of geodesic Voronoi diagrams on polyhedral terrains using a probabilistic analysis. Aronov et al. [2008] prove that, if one makes certain realistic input assumptions on the terrain, this complexity is...

All-Or-Nothing Generalized Assignment with Application to Scheduling Advertising Campaigns
Ron Adany, Moran Feldman, Elad Haramaty, Rohit Khandekar, Baruch Schieber, Roy Schwartz, Hadas Shachnai, Tami Tamir
Article No.: 38
DOI: 10.1145/2843944

We study a variant of the generalized assignment problem (gap), which we label all-or-nothing gap (agap). We are given a set of items, partitioned into n groups, and a set of m bins....

Sparse Text Indexing in Small Space
Philip Bille, Johannes Fischer, Inge Li Gørtz, Tsvi Kopelowitz, Benjamin Sach, Hjalte Wedel Vildhøj
Article No.: 39
DOI: 10.1145/2836166

In this work, we present efficient algorithms for constructing sparse suffix trees, sparse suffix arrays, and sparse position heaps for b arbitrary positions of a text T of length n while using only O(b) words of...

Point Line Cover: The Easy Kernel is Essentially Tight
Stefan Kratsch, Geevarghese Philip, Saurabh Ray
Article No.: 40
DOI: 10.1145/2832912

The input to the NP-hard point line cover problem (PLC) consists of a set P of n points on the plane and a positive integer k; the question is whether there exists a set of at most k lines that pass through...

On Problems as Hard as CNF-SAT
Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström
Article No.: 41
DOI: 10.1145/2925416

The field of exact exponential time algorithms for non-deterministic polynomial-time hard problems has thrived since the mid-2000s. While exhaustive search remains asymptotically the fastest known algorithm for some basic problems, non-trivial...

Approximation Algorithms for Stochastic Submodular Set Cover with Applications to Boolean Function Evaluation and Min-Knapsack
Amol Deshpande, Lisa Hellerstein, Devorah Kletenik
Article No.: 42
DOI: 10.1145/2876506

We present a new approximation algorithm for the stochastic submodular set cover (SSSC) problem called adaptive dual greedy. We use this algorithm to obtain a 3-approximation algorithm solving the stochastic Boolean function evaluation...

The Traveling Salesman Problem for Lines, Balls, and Planes
Adrian Dumitrescu, Csaba D. Tóth
Article No.: 43
DOI: 10.1145/2850418

We revisit the traveling salesman problem with neighborhoods (TSPN) and propose several new approximation algorithms. These constitute either first approximations (for hyperplanes, lines, and balls in Rd, for d ⩾ 3) or...

A Faster Algorithm for Computing Straight Skeletons
Siu-Wing Cheng, Liam Mencel, Antoine Vigneron
Article No.: 44
DOI: 10.1145/2898961

We present a new algorithm for computing the straight skeleton of a polygon. For a polygon with n vertices, among which r are reflex vertices, we give a deterministic algorithm that reduces the straight skeleton computation to a...