Navigation – Plan du site

NP-hardness of the computation of a median equivalence relation in classification (Régnier problem)

NP-difficulté de la détermination d’une relation d’équivalence médiane en classification (problème de Régnier)
Olivier Hudry
p. 83-97

Résumés

NP-difficulté de la détermination d’une relation d’équivalence médiane en classification (problème de Régnier)

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

Given a collection of equivalence relations (or partitions), Régnier’s problem consists in computing an equivalence relation which minimizes the remoteness from . The remoteness is based on the symmetric difference distance and measures the number of disagreements between and the considered equivalence relation. Such an equivalence relation minimizing the remoteness is called a median equivalence relation of . We prove the NP-hardness of Régnier’s problem, i.e. the computation of a median equivalence relation of a collection of equivalence relations, at least when the number of equivalence relations of is large enough.

Haut de page

Pour citer cet article

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 27 juin 2017. URL : http://msh.revues.org/12209

Haut de page

Auteur

Olivier Hudry

Télécom Paris Tech, 46, rue Barrault, 75634 Paris Cedex 13, olivier.hudry@telecom-paristech.fr

Articles du même auteur

Haut de page

Droits d’auteur

© École des hautes études en sciences sociales

Haut de page