A generalized insertion algorithm for the seriation problem
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.
- A generalized constructive algorithm using insertion-based heuristics
- Generalization of Schensted insertion algorithm to the cases of hooks and semi-shuffles
- An Optimal Algorithm for Strict Circular Seriation
- A Spectral Algorithm for Seriation and the Consecutive Ones Problem
- A Simple and Optimal Algorithm for Strict Circular Seriation
- A general method for improving insertion-based adaptive sorting
- On generalized comparison-based sorting problems
- scientific article; zbMATH DE number 5984
- An Algorithm for a Generalized Maximum Subsequence Problem
- A generalization of Gosper's algorithm
- A Dynamic Programming Formulation with Diverse Applications
- Computer Solutions of the Traveling Salesman Problem
- scientific article; zbMATH DE number 4147519 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1253047 (Why is no real title available?)
- Incidence matrices and interval graphs
- New Insertion and Postoptimization Procedures for the Traveling Salesman Problem
- Solving a family of permutation problems on 0-1 matrices
- SOME APPLICATIONS OF GRAPH THEORY AND RELATED NON‐METRIC TECHNIQUES TO PROBLEMS OF APPROXIMATE SERIATION: THE CASE OF SYMMETRIC PROXIMITY MEASURES
- The NP-completeness of the bandwidth minimization problem
- Using tabu search for solving a dynamic multi-terminal truck dispatching problem
- Flinders Petrie, the travelling salesman problem, and the beginning of mathematical modeling in archaeology
- Talent hold cost minimization in film production
- Matrix and Network Models in Archaeology
- scientific article; zbMATH DE number 4056860 (Why is no real title available?)
- A Spectral Algorithm for Seriation and the Consecutive Ones Problem
- \texttt{PQser:} a Matlab package for spectral seriation
- Fifty years of operational research: 1972--2022
This page was built for publication: A generalized insertion algorithm for the seriation problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1328867)
