A GENERALIZED INSERTION ALGORITHM FOR THE SERIATION PROBLEM

Given a binary matrix E, the Seriation Problem consists of determining a permutation of the rows of E minimizing the sum over all columns of the differences between the last and first nonzero element. This prob lem is derived from an archaeological context, but has applications in several other fields. We present a new generalized insertion heuristi c for this problem. The proposed heuristic outperforms other methods o n a series of benchmark problems.