NP-hardness of the computation of a median equivalence relation in classification (Régnier’s problem) - Département Informatique et Réseaux Accéder directement au contenu
Article Dans Une Revue Mathematics and Social Sciences Année : 2012

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

Résumé

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

Dates et versions

hal-02286265 , version 1 (13-09-2019)

Identifiants

  • HAL Id : hal-02286265 , version 1

Citer

Olivier Hudry. NP-hardness of the computation of a median equivalence relation in classification (Régnier’s problem). Mathematics and Social Sciences, 2012, 197, pp.83-97. ⟨hal-02286265⟩
43 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More