Abstract:
In applications ranging from DNA sequencing through archaeological dating to sparse matrix reordering, a recurrent problem is the sequencing of elements in such a way that highly correlated pairs of elements are near each other. That is, given a correlation function $f$ reflecting the desire for each pair of elements to be near each other, find all permutations p with the property that if p(i) < p(j) < p(k) then f(i,j) .ge. f(i,k) and $(j,k) .ge. f(i,k). This seriation problem is a generalization of the well studied consecutive ones problem. We present a spectral algorithm for this problem that has a number of interesting features. Whereas most previous applications of spectral techniques provide only bounds or heuristics, our result is an algorithm that correctly solves a nontrivial combinatorial problem. In addition, spectral methods are being successfully applied as heuristics to a variety of sequencing problems, and our result helps explain and justify these applications.