Utilisation des scores dans des méthodes exactes déterminant les ordres médians de tournois

Charon-Fournier, Irène; Germa, Anne; Hudry, Olivier

Mathématiques informatique et sciences humaines, Tome 119 (1992), pp. 53-74.

Dans cet article, nous utilisons un paramètre $\sigma \left(T\right)$ défini à partir des scores d’un tournoi $T$ pour déterminer les ordres médians de $T$. Ce paramètre évalue un éloignement entre le tournoi $T$ et les tournois transitifs ayant le même nombre de sommets. Appelant $i\left(T\right)$ le nombre minimum d’arcs à inverser pour rendre $T$ transitif, et $n$ le nombre de sommets de $T$, nous proposons d’abord deux algorithmes linéaires en n calculant $i\left(T\right)$ et un ordre médian de $T$ pour les tournois $T$ tels que $\sigma \left(T\right)$ soit égal à $1$ ou $2$. Puis nous donnons des résultats expérimentaux sur l’utilisation de $\sigma \left(T\right)$ dans une méthode arborescente par séparation et évaluation progressive («Branch and Bound») déterminant, pour tout tournoi $T,i\left(T\right)$ et les ordres médians de $T$.

In this paper, we use a parameter $\sigma \left(T\right)$ defined from the scores of a tournament $T$ to determine the median orders of $T$. This parameter measures a remoteness between the tournament $T$ and the transitive tournaments with the same number of vertices. Calling $i\left(T\right)$ the minimum number of arcs that it is necessary to reverse to make $T$ transitive, and $n$ the number of vertices of $T$, we give first two linear (in $n$) algorithms to compute $i\left(T\right)$ and a median order of $T$ for $T$ such that $\sigma \left(T\right)$ is equal to $1$ or $2$. Then we give experimental results on the use of $\sigma \left(T\right)$ in a Branch and Bound method designed to compute $i\left(T\right)$ and the median orders of $T$.

[1] Barthelemy J.-P., Guenoche A., Hudry O., "Median linear orders : heuristics and a branch and bound algorithm", European Journal of Operational Research 41 (1989), 313-325. | MR | Zbl

[1] Barthelemy J.-P., Monjardet B., "The median procedure in cluster analysis and social choice theory", Mathematical Social Sciences 1 (1981), 235-267. | MR | Zbl

[3] Charon-Fournier I., Germa A., Hudry O., "Encadrement de l'indice de Slater d'un tournoi à l'aide de ses scores", Mathématiques, Informatique et Sciences Humaines 118 (1992). | Numdam

[4] Guenoche A., "Order at minimum distance of a valued toumament", présenté à la Table Ronde Modélisation, Analyse et Agrégation des Préférences et des Choix (TRAP 3) (1988), Marseille-Luminy.

[5] Karp R.M., "Reducibility among combinatorial problems" in Complexity of computer computations, Miller et Tatcher éditeurs, Plenum Press, New York, 1972, 85-103. | MR

[6] Landau H.G. "On dominance relations and the structure of animal societies III. The condition for a score structure", Bulletin of Mathematical Biophysics 13 (1953),1-19. | MR

[7] Moon J.W., Topics on tournaments, Holt, New York,1968. | MR | Zbl

[8] Remage R., Thompson W.A., "Maximum likelihood paired comparison rankings", Biometrika 53 (1966), 143-149. | MR | Zbl

[9] Slater P. "Inconsistencies in a schedule of paired comparisons", Biometrika 53 (1961), 143-149.

[10] Smith A.F.M., Payne C.D., "An algorithm for determining Slater's i and all nearest adjoining orders", British Journal of Mathematical and Statistical Psychology 27 (1974), 49-52.

[11] Wakabayashi Y., Aggregation of binary relations : algorithmic and polyhedral investigations, PhD Thesis, Augsbourg, 1986. | Zbl

[12] Younger D.H., "Minimum feedback arc sets for a directed graph ", IEEE Trans. of the profes. tech. group in circuit theory 10, 2 (1963), 238-245.