We present an algorithm which attempts to align pairs of subsequences from a database of genetic sequences. The algorithm simulates the classical dynamic programming alignment algorithm over a suffix array of the database. ...

We study an approximation scheme to solve minimum cost multicommodity flow problems to a relative accuracy of epsilon is an element of (0, 1]. The proposed scheme, which we shall call Algorithm A, is a bisection-based ...

We explore the computational issues concerning a new algorithm for the classical least-squares approximation of N samples by an algebraic polynomial of degree at most n when the number N of the samples is very large. The ...

Given a set of n jobs with integral release dates, processing times and weights, it is a natural and important scheduling problem to compute a schedule that minimizes the sum of the weighted flow times of the jobs. There ...

Similarity join is a key operation in metric databases. It retrieves all pairs of elements that are similar. Solving such a problem usually requires comparing every pair of objects of the datasets, even when indexing and ...

Consider the Maximum Weight Independent Setproblem for rectangles: given a family ofweighted axis-parallel rectangles in the plane, find a maximum-weight subset of non-overlappingrectangles. The problem is notoriously hard ...

For a fixed family F of graphs, an F-packing in a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a natural ...

Finding low-cost spanning subgraphs with given degree and connectivity requirements is a fundamental problem in the area of network design. We consider the problem of finding d-regular spanning subgraphs (or d-factors) of ...