# Convex Relaxations for Permutation Problems

arXiv: https://arxiv.org/abs/1306.4805 · HTML: https://mlsanity.com/paper/1306.4805/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jun 2013.

## Built on by (most cited first, 14 of 14)

- [Git Re-Basin: Merging Models modulo Permutation Symmetries](https://mlsanity.com/paper/2209.04836/) (2022)
- [On the Symmetries of Deep Learning Models and their Internal Representations](https://mlsanity.com/paper/2205.14258/) (2022)
- [Smooth Non-Rigid Shape Matching via Effective Dirichlet Energy Optimization](https://mlsanity.com/paper/2210.02870/) (2022)
- [Q-Match: Iterative Shape Matching via Quantum Annealing](https://mlsanity.com/paper/2105.02878/) (2021)
- [Adiabatic Quantum Graph Matching with Permutation Matrix Constraints](https://mlsanity.com/paper/2107.04032/) (2021)
- [A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D Shape Matching](https://mlsanity.com/paper/2204.12805/) (2022)
- [Localization in 1D non-parametric latent space models from pairwise affinities](https://mlsanity.com/paper/2108.03098/) (2021)
- [Kernelized multi-graph matching](https://mlsanity.com/paper/2210.05206/) (2022)
- [Shuffled linear regression through graduated convex relaxation](https://mlsanity.com/paper/2209.15608/) (2022)
- [Scheduling Jobs with Stochastic Holding Costs](https://mlsanity.com/paper/2105.13655/) (2021)
- [Learning Bayesian Networks through Birkhoff Polytope: A Relaxation Method](https://mlsanity.com/paper/2107.01658/) (2021)
- [Active Seriation: Efficient Ordering Recovery with Statistical Guarantees](https://mlsanity.com/paper/2603.15336/) (2026)
- [Truncated Log-concave Sampling with Reflective Hamiltonian Monte Carlo](https://mlsanity.com/paper/2102.13068/) (2021)
- [iStructTab: Structured Feature Sequencing for Multimodal Learning of Image and Tabular Data](https://mlsanity.com/paper/2608.04348/) (2026)

## Abstract (arXiv)

Seriation seeks to reconstruct a linear order between variables using unsorted, pairwise similarity information. It has direct applications in archeology and shotgun gene sequencing for example. We write seriation as an optimization problem by proving the equivalence between the seriation and combinatorial 2-SUM problems on similarity matrices (2-SUM is a quadratic minimization problem over permutations). The seriation problem can be solved exactly by a spectral algorithm in the noiseless case and we derive several convex relaxations for 2-SUM to improve the robustness of seriation solutions in noisy settings. These convex relaxations also allow us to impose structural constraints on the solution, hence solve semi-supervised seriation problems. We derive new approximation bounds for some of these relaxations and present numerical experiments on archeological data, Markov chains and DNA assembly from shotgun gene sequencing data.