Relaxations convexes pour les problèmes de permutation.

Résumé La sériation cherche à reconstruire un ordre linéaire entre les variables en utilisant des informations de similarité non triées. Elle a des applications directes en archéologie et en séquençage génétique shotgun par exemple. Nous prouvons l'équivalence entre la sériation et le problème combinatoire 2-sum (un problème de minimisation quadratique sur les permutations) sur une classe de matrices de similarité. Le problème de la sériation peut être résolu exactement par un algorithme spectral dans le cas sans bruit et nous produisons une relaxation convexe pour le problème de la somme 2 afin d'améliorer la robustesse des solutions dans un cadre bruyant. Cette relaxation nous permet également d'imposer des contraintes structurelles supplémentaires sur la solution, afin de résoudre les problèmes de sériation semi-supervisée. Nous présentons des expériences numériques sur des données archéologiques, des chaînes de Markov et des séquences de gènes.