Groupe d’études et de recherche en analyse des décisions


A Generalized Insertion Algorithm for the Seriation Problem

, et

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 non-zero element. This problem is derived from an archaeological context, but has applications in several other fields. We present a new generalized insertion heuristic for this problem. The proposed heuristic outperforms other methods on a series of benchmark problems.

, 15 pages