Utilisation des scores dans des méthodes exactes déterminant les ordres médians de tournois
Mathématiques et Sciences humaines, Volume 119  (1992), p. 53-74

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

Dans cet article, nous utilisons un paramètre σ(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 σ(T) soit égal à 1 ou 2. Puis nous donnons des résultats expérimentaux sur l’utilisation de σ(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.

@article{MSH_1992__119__53_0,
     author = {Charon, Ir\`ene and Germa, Anne and Hudry, Olivier},
     title = {Utilisation des scores dans des m\'ethodes exactes d\'eterminant les ordres m\'edians de tournois},
     journal = {Math\'ematiques et Sciences humaines},
     publisher = {Ecole des hautes-\'etudes en sciences sociales},
     volume = {119},
     year = {1992},
     pages = {53-74},
     zbl = {0845.05050},
     mrnumber = {1195698},
     language = {fr},
     url = {http://www.numdam.org/item/MSH_1992__119__53_0}
}
Charon-Fournier, Irène; Germa, Anne; Hudry, Olivier. Utilisation des scores dans des méthodes exactes déterminant les ordres médians de tournois. Mathématiques et Sciences humaines, Volume 119 (1992) , pp. 53-74. http://www.numdam.org/item/MSH_1992__119__53_0/

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