Search ACM DL

Search Issue

enter search term and/or author name

**Approximation algorithms for data placement on parallel disks**

Leana Golubchik, Sanjeev Khanna, Samir Khuller, Ramakrishna Thurimella, An Zhu

Article No.: 34

DOI: 10.1145/1597036.1597037

We study an optimization problem that arises in the context of data placement in a multimedia storage system. We are given a collection of *M* multimedia objects (data objects) that need to be assigned to a storage system consisting of...

**Sublinear estimation of entropy and information distances**

Sudipto Guha, Andrew McGregor, Suresh Venkatasubramanian

Article No.: 35

DOI: 10.1145/1597036.1597038

In many data mining and machine learning problems, the data items that need to be clustered or classified are not arbitrary points in a high-dimensional space, but are distributions, that is, points on a high-dimensional simplex. For...

**A generalized minimum cost k-clustering**

Asaf Levin

Article No.: 36

DOI: 10.1145/1597036.1597039

We consider the problems of set partitioning into *k* clusters with minimum total cost and minimum of the maximum cost of a cluster. The cost function is given by an oracle, and we assume that it satisfies some natural structural constraints....

**Bootstrapping a hop-optimal network in the weak sensor model**

Martin Farach-Colton, Rohan J. Fernandes, Miguel A. Mosteiro

Article No.: 37

DOI: 10.1145/1597036.1597040

Sensor nodes are very weak computers that get distributed at random on a surface. Once deployed, they must wake up and form a radio network. Sensor network bootstrapping research thus has three parts: One must model the restrictions on sensor...

**All maximal independent sets and dynamic dominance for sparse graphs**

David Eppstein

Article No.: 38

DOI: 10.1145/1597036.1597042

We describe algorithms, based on Avis and Fukuda's reverse search paradigm, for listing all maximal independent sets in a sparse graph in polynomial time and delay per output. For bounded degree graphs, our algorithms take constant time per set...

**A linear-time algorithm to find a separator in a graph excluding a minor**

Bruce Reed, David R. Wood

Article No.: 39

DOI: 10.1145/1597036.1597043

Let *G* be an *n*-vertex *m*-edge graph with weighted vertices. A pair of vertex sets *A*, *B* ⊆ *V*(*G*) is a 2/3*-separation* of *order* |*A* ∩ *B*| if *A* ∪...

**Enumeration of isolated cliques and pseudo-cliques**

Hiro Ito, Kazuo Iwama

Article No.: 40

DOI: 10.1145/1597036.1597044

In this article, we consider *isolated* cliques and *isolated* dense subgraphs. For a given graph *G*, a vertex subset *S* of size *k* (and also its induced subgraph *G*(*S*)) is said to be *c*-isolated if...

**A better approximation ratio for the vertex cover problem**

George Karakostas

Article No.: 41

DOI: 10.1145/1597036.1597045

We reduce the approximation factor for the vertex cover to 2 − Θ (1/&sqrt;log*n*) (instead of the previous 2 − Θ ln ln *n*/2ln *n* obtained by Bar-Yehuda and Even [1985] and Monien and Speckenmeyer [1985])....

**A linear algorithm for computing convex hulls for random lines**

Daniel Berend, Vladimir Braverman

Article No.: 42

DOI: 10.1145/1597036.1597046

Finding the convex hull of *n* points in the plane requires *O*(*n* log *n*) time in general. In Devroye and Toussaint [1993] and Golin et al. [2002] the problem of computing the convex hull of the intersection points of...

**Randomized fast design of short DNA words**

Ming-Yang Kao, Manan Sanghi, Robert Schweller

Article No.: 43

DOI: 10.1145/1597036.1597047

We consider the problem of efficiently designing sets (codes) of equal-length DNA strings (words) that satisfy certain combinatorial constraints. This problem has numerous motivations including DNA self-assembly and DNA computing. Previous work...

**Parametric analysis for ungapped Markov models of evolution**

David Fernández-Baca, Balaji Venkatachalam

Article No.: 44

DOI: 10.1145/1597036.1597048

Efficient sensitivity analysis algorithms are presented for two problems arising in the study of Markov models of sequence evolution: ancestral reconstruction in evolutionary trees and local ungapped alignment under log-odds scoring. The...

**Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function**

Alexander D. Scott, Gregory B. Sorkin

Article No.: 45

DOI: 10.1145/1597036.1597049

We introduce a problem class we call Polynomial Constraint Satisfaction Problems, or PCSP. Where the usual CSPs from computer science and optimization have real-valued score functions, and partition functions from physics have monomials, PCSP has...

**Low-dimensional lattice basis reduction revisited**

Phong Q. Nguyen, Damien Stehlé

Article No.: 46

DOI: 10.1145/1597036.1597050

Lattice reduction is a geometric generalization of the problem of computing greatest common divisors. Most of the interesting algorithmic problems related to lattice reduction are NP-hard as the lattice dimension increases. This article deals with...