Details

Autor(en) / Beteiligte

• Atkins, Jonathan E.
• Boman, Erik G.
• Hendrickson, Bruce

Titel

A Spectral Algorithm for Seriation and the Consecutive Ones Problem

Ist Teil von

• SIAM journal on computing, 1998-01, Vol.28 (1), p.297-310

Ort / Verlag

Philadelphia: Society for Industrial and Applied Mathematics

Erscheinungsjahr

1998

Link zum Volltext

Quelle

EBSCOhost Business Source Ultimate

Beschreibungen/Notizen

• In applications ranging from DNA sequencing through archeological 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 $\pi$ with the property that if $\pi(i) < \pi(j) < \pi(k)$ then $f(i,j) \ge f(i,k)$ and $f(j,k) \ge f(i,k)$. This seriationproblem 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.