|
Modify search criterions Results n° 1 to 8 of 27 matches Read the article
Read the article
| Title |
NP-hardness of the computation of a median equivalence relation in classification (Régnier’s problem) |
| Author |
HUDRY Olivier |
| Keywords |
Aggregation of relations, Classification, Complexity, Equivalence relation, Median relation, NP-completeness, Partition, Régnier's problem, Symmetric difference distance, Zahn's problem |
| Topic |
None |
| Abstract |
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. |
| Number |
197, Spring 2012, special issue: Categories, classification, complexity, consensus ... Around Jean-Pierre Barthélemy's works |
| Language |
English | Read the article
Read the article
Read the article
| Title |
Consensus theories, an oriented survey |
| Author |
MONJARDET Bernard, HUDRY Olivier |
| Keywords |
Aggregation rule, Arrowian result, Complexity, Consensus theory, Distance, Lower valuation, Median semilattice, Médiane, Restricted domain, Tournament solution |
| Topic |
None |
| Abstract |
This article surveys seven directions of consensus theories: Arrowian results, federation consensus rules, metric consensus rules, tournament solutions, restricted domains, abstract consensus theories, algorithmic and complexity issues. This survey is oriented in the sense that it is mainly - but not exclusively - concentrated on the most significant results obtained, sometimes with other researchers, by a team of French researchers who are or were full or associate members of the Centre d'analyse et de mathématique sociale (CAMS). |
| Number |
190, Summer 2010, special issue: Theories and uses. Tribute issue to Bruno Leclerc |
| Language |
English | Read the article
| Title |
Nathalie Caspard, Bruno Leclerc, Bernard Monjardet, "Ensembles ordonnés finis : concepts, résultats et usages", Springer, Berlin, Heidleberg, 2007. |
| Author |
HUDRY Olivier |
| Keywords |
None |
| Topic |
None |
| Abstract |
Book review |
| Number |
190, Summer 2010, special issue: Theories and uses. Tribute issue to Bruno Leclerc |
| Language |
French | Read the article
Read the article
Users rights :

The entire journal is licensed under a Creative Commons license
|