Search ACM DL

Search Issue

enter search term and/or author name

**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* = {*t _{i}*} wishes to send traffic to a root

**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...