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 et Sciences humaines, Tome 120 (1992), p. 53-74 / Harvested from Numdam

Résumé

Dans cet article, nous utilisons un paramètre $\sigma (T)$ 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(T)$ 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(T)$ et un ordre médian de $T$ pour les tournois $T$ tels que $\sigma (T)$ soit égal à $1$ ou $2$. Puis nous donnons des résultats expérimentaux sur l’utilisation de $\sigma (T)$ dans une méthode arborescente par séparation et évaluation progressive («Branch and Bound») déterminant, pour tout tournoi $T, i(T)$ et les ordres médians de $T$.

Abstract

In this paper, we use a parameter $\sigma (T)$ 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(T)$ 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(T)$ and a median order of $T$ for $T$ such that $\sigma (T)$ is equal to $1$ or $2$. Then we give experimental results on the use of $\sigma (T)$ in a Branch and Bound method designed to compute $i(T)$ and the median orders of $T$.

Détail

Publié le : 1992-01-01

MR 1195698 | Zbl 0845.05050 | 3 citations dans Numdam

Bibliographie

[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 1020904 | Zbl 0689.90003

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

[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 378476

[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 41412

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

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

[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 0606.68036

[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.