Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 11 Issue 1, October 2014

Aravind Srinivasan
Article No.: 1e
DOI: 10.1145/2675311

Gathering Despite Mischief
Yoann Dieudonné, Andrzej Pelc, David Peleg
Article No.: 1
DOI: 10.1145/2629656

A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, have to meet at the same node. Agents move in synchronous rounds. Each agent has a different label. Up to f of the agents are...

Distributed Selfish Load Balancing on Networks
Petra Berenbrink, Martin Hoefer, Thomas Sauerwald
Article No.: 2
DOI: 10.1145/2629671

We study distributed load balancing in networks with selfish agents. In the simplest model considered here, there are n identical machines represented by vertices in a network and mn selfish agents that unilaterally...

Better Scalable Algorithms for Broadcast Scheduling
Nikhil Bansal, Ravishankar Krishnaswamy, Viswanath Nagarajan
Article No.: 3
DOI: 10.1145/2636916

In the classical broadcast scheduling problem, there are n pages stored at a server, and requests for these pages arrive over time. Whenever a page is broadcast, it satisfies all outstanding requests for that page. The objective is...

Constraint Solving via Fractional Edge Covers
Martin Grohe, Dániel Marx
Article No.: 4
DOI: 10.1145/2636918

Many important combinatorial problems can be modeled as constraint satisfaction problems. Hence, identifying polynomial-time solvable classes of constraint satisfaction problems has received a lot of attention. In this article, we are interested...

Approximation Algorithms for Min-Max Generalization Problems
Piotr Berman, Sofya Raskhodnikova
Article No.: 5
DOI: 10.1145/2636920

We provide improved approximation algorithms for the min-max generalization problems considered by Du, Eppstein, Goodrich, and Lueker [Du et al. 2009]. Generalization is widely used in privacy-preserving data mining and can also be viewed...

Union-Find with Constant Time Deletions
Stephen Alstrup, Mikkel Thorup, Inge Li Gørtz, Theis Rauhe, Uri Zwick
Article No.: 6
DOI: 10.1145/2636922

A union-find data structure maintains a collection of disjoint sets under the operations makeset, union, and find. Kaplan, Shafrir, and Tarjan [SODA 2002] designed data structures for an extension of the union-find problem in which items of the...

Annotations in Data Streams
Amit Chakrabarti, Graham Cormode, Andrew Mcgregor, Justin Thaler
Article No.: 7
DOI: 10.1145/2636924

The central goal of data stream algorithms is to process massive streams of data using sublinear storage space. Motivated by work in the database community on outsourcing database and data stream processing, we ask whether the space usage...