Résumé de séminaire

Résumé :

Étant donnée une n × n dissimilarité D, elle a la propriété de Robinson si elle satisfait l'anti-inégalité du triangle bottleneck: max(d_ij , d_jk ) >= d_ik pour tout 1 <= i < j < k <= n. Nous transportons cette condition du triangle à diverses conditions sur le quadrangle et caractérisons les cônes de matrices 0-1 associés. L'exposé s'articule autour des enjeux d'une approximation d'une dissimilarité quelconque par une dissimilarité satisfaisant l'une des propriétés (Kalmanson, van der Veen, Supnick...) puis une présentation des techniques mises en oeuvre pour caractériser un cône particulier tant du point de vue de sa structure que du dénombrement par des fonctions génératrices.

Mots clés : Kalmanson, Robinson, bottleneck Monge, extremal rays, seriation, clustering.

Références :

Email : Dominique.Fortin@inria.fr, Pascal.Prea@lif.univ-mrs.fr

Les transparents en pdf de D. Fortin.