Agrégation des similarités : une solution oubliée
RAIRO - Operations Research - Recherche Opérationnelle, Tome 36 (2002) no. 1, pp. 101-108.

Le problème de l'agrégation des similarités signées est résolu à l'aide d'une version dérivant de l'algorithme booléen de Faure et Malgrange. La méthode s'applique à des similarités entières ou réelles, et permet l'énumération des solutions multiples. Elle nécessite une quantité de mémoire égale à trois fois la taille des données d'entrée.

The signed similarities aggregation problem is solved with a boolean method derived from the Faure and Malgrange algorithm. The method is adequate either for integer similarities or real similarites, and multiple solutions can be enumerated. It needs a space amount equal to three times the input data size.

DOI : https://doi.org/10.1051/ro:2002001
Mots clés : agrégation des similarités, partition optimale, programmation linéaire en variables booléennes
@article{RO_2002__36_1_101_0,
     author = {Petitjean, Michel},
     title = {Agr\'egation des similarit\'es : une solution oubli\'ee},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {101--108},
     publisher = {EDP-Sciences},
     volume = {36},
     number = {1},
     year = {2002},
     doi = {10.1051/ro:2002001},
     zbl = {1027.90073},
     language = {fr},
     url = {http://www.numdam.org/articles/10.1051/ro:2002001/}
}
Petitjean, Michel. Agrégation des similarités : une solution oubliée. RAIRO - Operations Research - Recherche Opérationnelle, Tome 36 (2002) no. 1, pp. 101-108. doi : 10.1051/ro:2002001. http://www.numdam.org/articles/10.1051/ro:2002001/

[1] J.S. deCani, A Branch and Bound Algorithm for Maximum Likelihood Paired Comparison Ranking. Biometrika 59 (1972) 131-135. | MR 319322 | Zbl 0245.62037

[2] F. Faure, La programmation linéaire appliquée, Collection “Que sais-je ?”, No. 1776, Chap. 4. Presses Universitaires de France, Paris (1979).

[3] M. Grötschel et Y. Wakabayashi, A Cutting Plane Algorithm for a Clustering Problem. Math. Prog. Ser. B 45 (1989) 59-96. | MR 1017212 | Zbl 0675.90072

[4] I.C. Lerman, Classification et analyse ordinale des données, Chap. 1.3. Dunod Ed., Bordas, Paris (1981). | MR 645150

[5] F. Marcotorchino, Agrégation des similarités en classification automatique, Ph.D. Thesis. Université Paris VI, France (1981).

[6] J.-F. Marcotorchino et P. Michaud, Optimisation an analyse ordinale des données, Chap. X, Collection : Statistiques et décisions économiques. Masson, Paris (1979).

[7] P. Michaud, Agrégation à la majorité II : analyse du résultat d'un vote. Centre Scientifique IBM France, Étude F.052, Paris (1985).

[8] P. Michaud, Hommage à Condorcet (version intégrale pour le bicentenaire de l'essai de Condorcet). Centre Scientifique IBM France, Étude F.094, Paris (1985).

[9] M. Minoux, Programmation mathématique. Théorie et algorithmes, Vol. 2, Chap. 7, Collection technique et scientifique des Télécommunications. CNET-ENST Eds., Bordas, Paris (1983). | Zbl 0546.90056

[10] M. Petitjean, Applications of the Radius-Diameter Diagram to the Classification of Topological and Geometrical Shapes of Chemical Compounds. J. Chem. Inf. Comput. Sci. 32 (1992) 331-337.

[11] Roseaux, Exercices et problèmes résolus de recherche opérationnelle, Tome 3, Chap. III. Masson, Paris (1985).

[12] G. Saporta, Probabilités, analyse des données et statistique, Chap. 12, Sections 12.1 et 12.2. Technip, Paris (1990). | Zbl 0703.62003

[13] A. Schrijver, Theory of Linear and Integer Programming, Part IV. John Wiley and Sons, New-York (1986). | MR 874114 | Zbl 0665.90063

[14] G. Sierksma, Linear and Integer Prpgramming. Theory and Practice. Marcel Dekker Inc., New-York, Monogr. and Textbooks in Pure Appl. Math. 198 (1996). | MR 1449398 | Zbl 0885.90080

[15] G. Vernin et M. Petitjean, Application de la méthode de recherche de partition centrale sur variables pondérées à la classification des vins. Étude préliminaire. Rev. Fr. Oenol. (Cahier Scientifique) 31 (1991) 7-15.