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

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.

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.

@article{MSH_1992__119__53_0,
     author = {Charon-Fournier, 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 informatique et sciences humaines},
     pages = {53--74},
     publisher = {Ecole des hautes-\'etudes en sciences sociales},
     volume = {119},
     year = {1992},
     mrnumber = {1195698},
     zbl = {0845.05050},
     language = {fr},
     url = {http://archive.numdam.org/item/MSH_1992__119__53_0/}
}
TY  - JOUR
AU  - Charon-Fournier, Irène
AU  - Germa, Anne
AU  - Hudry, Olivier
TI  - Utilisation des scores dans des méthodes exactes déterminant les ordres médians de tournois
JO  - Mathématiques informatique et sciences humaines
PY  - 1992
SP  - 53
EP  - 74
VL  - 119
PB  - Ecole des hautes-études en sciences sociales
UR  - http://archive.numdam.org/item/MSH_1992__119__53_0/
LA  - fr
ID  - MSH_1992__119__53_0
ER  - 
%0 Journal Article
%A Charon-Fournier, Irène
%A Germa, Anne
%A Hudry, Olivier
%T Utilisation des scores dans des méthodes exactes déterminant les ordres médians de tournois
%J Mathématiques informatique et sciences humaines
%D 1992
%P 53-74
%V 119
%I Ecole des hautes-études en sciences sociales
%U http://archive.numdam.org/item/MSH_1992__119__53_0/
%G fr
%F 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 informatique et sciences humaines, Tome 119 (1992), pp. 53-74. http://archive.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 | 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.