NP-hardness of the computation of a median equivalence relation in classification (Régnier problem)
É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...
Gorde:
| Argitaratua izan da: | URI:https://journals.openedition.org/msh, |
|---|---|
| Egile nagusia: | |
| Formatua: | Article ou chapitre numérique |
| Hizkuntza: | Français |
| Argitaratua: |
Mathématiques et sciences humaines
2012
|
| Gaiak: | |
| Sarrera elektronikoa: | Accès Université d'Orléans et IFPM Accès Université d'Orléans et IFPM |
| Gaia: | É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. |
|---|