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

Mathématiques et sciences humaines. Mathematics and social sciences

Hudry, Olivier¹ 

关键词: classification;    relation;    partition;    complexity;    median;    symmetric difference distance;    aggregation of relations;    equivalence relation;    NP-completeness;    Régnier’s problem;    Zahn’s problem;   

DOI  :  10.4000/msh.12209

学科分类：数学（综合）

来源: College de France * Ecole des Hautes Etudes en Sciences Sociales (E H E S S)

【 摘 要 】

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.

【 授权许可】

Unknown