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

DOI10.4000/msh.12209zbMath1288.91069OpenAlexW117079032MaRDI QIDQ5412503

Olivier Hudry

Publication date: 25 April 2014

Published in: Mathématiques et sciences humaines (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4000/msh.12209

zbMATH Keywords

classificationcomplexitypartitionNP-completenessequivalence relationsymmetric difference distanceZahn's problemmedian relationRégnier's problemaggregation of relations

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Social choice (91B14)

Related Items (2)

A statistical view of clustering performance through the theory of \(U\)-processes ⋮ Application of the “descent with mutations” metaheuristic to a clique partitioning problem

This page was built for publication: NP-hardness of the computation of a median equivalence relation in classification (Régnier problem)