ACM DL

Algorithms (TALG)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Algorithms (TALG), Volume 5 Issue 4, October 2009

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, BV(G) is a 2/3-separation of order |AB| 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;logn) (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...