Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 4 Issue 2, May 2008

Guest editorial
Adam L. Buchsbaum
Article No.: 16
DOI: 10.1145/1361192.1361193

Compact dictionaries for variable-length keys and data with applications
Daniel K. Blandford, Guy E. Blelloch
Article No.: 17
DOI: 10.1145/1361192.1361194

We consider the problem of maintaining a dynamic dictionary T of keys and associated data for which both the keys and data are bit strings that can vary in length from zero up to the length w of a machine word. We present a data...

Provably good moving least squares
Ravikrishna Kolluri
Article No.: 18
DOI: 10.1145/1361192.1361195

We analyze a moving least squares (MLS) interpolation scheme for reconstructing a surface from point cloud data. The input is a sufficiently dense set of sample points that lie near a closed surface F with approximate surface...

Dissections, orientations, and trees with applications to optimal mesh encoding and random sampling
Éric Fusy, Gilles Schaeffer, Dominique Poulalhon
Article No.: 19
DOI: 10.1145/1361192.1361196

We present a bijection between some quadrangular dissections of an hexagon and unrooted binary trees with interesting consequences for enumeration, mesh compression, and graph sampling. Our bijection yields an efficient uniform random sampler for...

Primal-dual approach for directed vertex connectivity augmentation and generalizations
László A. Végh, András A. Benczúr
Article No.: 20
DOI: 10.1145/1361192.1361197

In their seminal paper, Frank and Jordán [1995] show that a large class of optimization problems, including certain directed graph augmentation, fall into the class of covering supermodular functions over pairs of sets. They also...

An asymptotic approximation scheme for multigraph edge coloring
Peter Sanders, David Steurer
Article No.: 21
DOI: 10.1145/1361192.1361198

The edge coloring problem considers the assignment of colors from a minimum number of colors to edges of a graph such that no two edges with the same color are incident to the same node. We give polynomial time algorithms for approximate edge...

Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
Shuchi Chawla, Anupam Gupta, Harald Räcke
Article No.: 22
DOI: 10.1145/1361192.1361199

In this article, we study metrics of negative type, which are metrics (V, d) such that &sqrt;d is an Euclidean metric; these metrics are thus also known as ℓ2-squared metrics. We show how to embed n-point...

On the approximability of some network design problems
Julia Chuzhoy, Anupam Gupta, Joseph (Seffi) Naor, Amitabh Sinha
Article No.: 23
DOI: 10.1145/1361192.1361200

Consider the following classical network design problem: a set of terminals T = {ti} wishes to send traffic to a root r in an n-node graph G = (V, E). Each...

Limitations of cross-monotonic cost-sharing schemes
Nicole Immorlica, Mohammad Mahdian, Vahab S. Mirrokni
Article No.: 24
DOI: 10.1145/1361192.1361201

A cost-sharing scheme is a set of rules defining how to share the cost of a service (often computed by solving a combinatorial optimization problem) amongs serviced customers. A cost-sharing scheme is cross-monotonic if it satisfies the property...