NP-hardness of the computation of a median equivalence relation in classification (Régnier problem)
Résumés
Étant donnée une collection de relations d’équivalence (ou partitions), le problème de Régnier consiste à déterminer une relation d’équivalence qui minimise l’éloignement par rapport à . L’éloignement est fondé sur la distance de la différence symétrique et mesure le nombre de désaccords entre et la relation d’équivalence considérée. Une telle relation d’équivalence minimisant l’éloignement est appelée une relation d’équivalence médiane de . On montre ici la NP-difficulté du problème de Régnier, c’est-à-dire du calcul d’une relation d’équivalence médiane d’une collection de relations d’équivalence, du moins quand le nombre de relations d’équivalence de est suffisamment grand.
Entrées d’index
Mots-clés :
aggregation de relations, classification, complexité, distance de la difference symétrique, NP-complétude, partition, problem de Régnier, problem de Zahn, relation d’équivalence, relation médianeKeywords:
aggregation of relations, classification, complexity, equivalence relation, median, NP-completeness, partition, Régnier’s problem, relation, symmetric difference distance, Zahn’s problemPour citer cet article
Référence papier
Olivier Hudry, « NP-hardness of the computation of a median equivalence relation in classification (Régnier problem) », Mathématiques et sciences humaines, 197 | 2012, 83-97.
Référence électronique
Olivier Hudry, « NP-hardness of the computation of a median equivalence relation in classification (Régnier problem) », Mathématiques et sciences humaines [En ligne], 197 | Printemps 2012, mis en ligne le 02 mai 2012, consulté le 05 décembre 2025. URL : http://journals.openedition.org/msh/12209 ; DOI : https://doi.org/10.4000/msh.12209
Haut de pageDroits d’auteur
Le texte et les autres éléments (illustrations, fichiers annexes importés), sont « Tous droits réservés », sauf mention contraire.
Haut de page
