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

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

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

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

Résumé
Abstract

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

EuDML MR Zbl | 3 citations dans Numdam

@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 = {https://www.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  - https://www.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 https://www.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. https://www.numdam.org/item/MSH_1992__119__53_0/

Bibliographie
Cité par

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