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 鈥減lus proche possible鈥� de l鈥檈nsemble de d茅part, sous une certaine distance. Ce probl猫me est inspir茅 d鈥檜n probl猫me classique en g茅nomique comparative o霉 les diff茅rences entre les ordres d鈥檃pparition 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鈥檕rdre d鈥檃pparition de paires d鈥櫭﹍茅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鈥檈space de recherche pour les m茅dianes de cet ensemble. D鈥檜n 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鈥檕rdre d鈥檃pparition de paires d鈥櫭﹍茅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鈥檈space de recherche pour les m茅dianes de cet ensemble. D鈥檜n 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).