A generalized insertion algorithm for the seriation problem (Q1328867): Difference between revisions

Consider the following problem: Let \(E\) be an \(n\times m\) matrix of 0's and 1's. We are going to permute the rows of \(E\). We hope that when we are finished permuting the distance between the top most 1 and the bottom most 1 in most of the columns is fairly small. More formally we want to find the permutation of rows of \(E\) such that the resulting matrix minimizes the score of the matrix defined as \(\sum_{j=1}^ m (\beta_ j - \alpha_ j)\) where \(\alpha_ j\) and \(\beta_ j\) are the row numbers of the first and last 1 in column \(j\). This problem has applications to archeology. The authors take a previous algorithm that they used for the Traveling Salesperson Problem and adapt it to this problem. It works quite well on several test cases and outperforms prior algorithms.