Event
Sylvie Hamel, Université de Montréal
MĂ©dianes de permutations sous la distance de Kendall-tau
Étant donné un ensemble de permutations le problème de la médiane consiste à trouver une permutation qui est la “plus proche possible” de l’ensemble de départ, sous une certaine distance. Ce problème est inspiré d’un problème classique en génomique comparative où les différences entre les ordres d’apparition de gènes dans différents génomes sont utilisées pour déduire des distances évolutives entre ces génomes.
Dans cette conférence, nous nous intéressons au problème de la médiane sous la distance de Kendall-tau qui compte le nombre de désaccords entre l’ordre d’apparition de paires d’éléments de deux permutations. Ce problème a été montré NP-complet pour des ensembles de $m$ permutations, où $m$ est pair et $m > 3$. La complexité est inconnue pour les cas impairs et lorsque $m = 3$. D'un point de vue algorithmique, nous allons présenter quelques propriétés théoriques de l'ensemble de départ de permutations qui réduisent considérablement l’espace de recherche pour les médianes de cet ensemble. D’un point de vue plus combinatoire, nous allons considérer le cas intéressant des ensembles automédians (quand un ensemble de permutations est égal à l'ensemble de ses médianes).
Dans cette conférence, nous nous intéressons au problème de la médiane sous la distance de Kendall-tau qui compte le nombre de désaccords entre l’ordre d’apparition de paires d’éléments de deux permutations. Ce problème a été montré NP-complet pour des ensembles de $m$ permutations, où $m$ est pair et $m > 3$. La complexité est inconnue pour les cas impairs et lorsque $m = 3$. D'un point de vue algorithmique, nous allons présenter quelques propriétés théoriques de l'ensemble de départ de permutations qui réduisent considérablement l’espace de recherche pour les médianes de cet ensemble. D’un point de vue plus combinatoire, nous allons considérer le cas intéressant des ensembles automédians (quand un ensemble de permutations est égal à l'ensemble de ses médianes).