enter search term and/or author name
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
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...
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
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
Article No.: 38
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
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
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
Article No.: 41
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  and Monien and Speckenmeyer )....
A linear algorithm for computing convex hulls for random lines
Daniel Berend, Vladimir Braverman
Article No.: 42
Finding the convex hull of n points in the plane requires O(n log n) time in general. In Devroye and Toussaint  and Golin et al.  the problem of computing the convex hull of the intersection points of...
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
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
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...
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...