A SPECTRAL ALGORITHM FOR SERIATION AND THE CONSECUTIVE ONES PROBLEM

In applications ranging from DNA sequencing through archeological dati ng 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 t he desire for each pair of elements to be near each other, find all pe rmutations pi with the property that if pi(i) < pi(j) < pi(k) then f(i , j) greater than or equal to f(i, k) and f(j, k) greater than or equa l to f(i, k). This seriation problem is a generalization of the well-s tudied consecutive ones problem. We present a spectral algorithm for t his problem that has a number of interesting features. Whereas most pr evious applications of spectral techniques provide only bounds or heur istics, our result is an algorithm that correctly solves a nontrivial combinatorial problem. In addition, spectral methods are being success fully applied as heuristics to a variety of sequencing problems, and o ur result helps explain and justify these applications.