Étude combinatoire et algorithmique de la médiane de permutations sous la distance de Kendall-Tau

Abstract

Une permutation peut être vue comme un classement qui ordonne des éléments ou des candidats en fonction d’une préférence ou d’un critère. Ce classement peut être le vote d’un électeur qui doit classer tous les candidats en ordre de préférence, le résultat d’une compétition sportive avec plusieurs athlètes ou encore une liste des meilleurs films de 2018. Cependant, il se peut, dans les exemples ci-dessus, que les électeurs n’aient pas les mêmes préférences ou encore qu’une compétition sportive soit divisée en plusieurs épreuves dont les classements diffèrent les uns des autres. C’est pourquoi il existe des règles pour générer une permutation "consensus", c’est-à-dire qui est le meilleur compromis entre les différents classements. L’un de ces consensus est la médiane de permutation, appelée aussi consensus de Kemeny. Cette dernière méthode respecte un ensemble de propriétés qui justifient son utilisation. Le calcul du consensus de Kemeny est toutefois un problème NP-difficile. Conséquemment, de nombreux travaux de recherche ont été effectués sur le sujet. Ce mémoire étudie principalement des classes spéciales du problème, c’est-à-dire le calcul du consensus de Kemeny d’un ensemble de permutations présentant des caractéristiques spécifiques.

A permutation can be seen as a ranking which orders elements or candidates by a criteria or a preference. This ranking can be an elector’s vote to rank candidates in order of preference, athletes in a sports competition or a list of the best movies of 2018. However, in these examples, the electors may not all have the same preferences and the athletes might be judged on more than one challenge in which rankings differ. This is why "consensus" rules of permutation exist as the best compromise for the different rankings. One of these consensus is the median permutation, or the Kemeny consensus. This method respects some properties which justify its use, but is NP-hard to compute. Consequently, numerous researchers have devoted time to study this problem. This master’s thesis aims to study the calculation of the Kemeny consensus in special cases of the problem, which are set of permutations with specific characteristics.