| Accueil |
| Dernière Parution |
| Auteurs |
| Thèmes |
| Mots-clefs |
| Parutions |
| Videos |
| Recherche guidée |
| Comité de lecture |
| Contact |
| Abonnement |
| Soumission d'article |
Version anglaise |
Collection numérisée également sur NUMDAM pour les n°1 à n°148 et sur Revues.org pour les n° 149 et suivants |
- Recherche selon le critère:
- Mot-clef: Complexité
2 entrées référencées
| Titre | NP-difficulté de la détermination d’une relation d’équivalence médiane en classification (problème de Régnier) |
| Auteur | HUDRY Olivier |
| Mots-clefs | Agrégation de relations, Classification, Complexité, Distance de la différence symétrique, NP-complétude, Partition, Problème de Régnier, Problème de Zahn, Relation d'équivalence, Relation médiane |
| Thème | Aucun |
| Résumé | É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. |
| Numéro | 197, Printemps 2012, n° spécial Catégories, classification, complexité, consensus... Autour des travaux de Jean-Pierre Barthélemy |
| Langue | Anglais |
| Titre | Théories du consensus. Une synthèse orientée |
| Auteur | MONJARDET Bernard, HUDRY Olivier |
| Mots-clefs | Complexité, Demi-treillis à médianes, Distance, Domaine restreint, Médiane, Règle d'agrégation, Résultat arrowien, Solution de tournoi, Théorie du consensus, Valuation inférieure |
| Thème | Aucun |
| Résumé | Cet article présente une vue d'ensemble de sept directions de recherche en théorie du consensus : résultats arrowiens, règles d'agrégation définies au moyen de fédérations, règles définies au moyen de distances, solutions de tournoi, domaines restreints, théories abstraites du consensus, questions de complexité et d'algorithmique. Ce panorama est orienté dans la mesure où il présente principalement - mais non exclusivement - les travaux les plus significatifs obtenus - quelquefois avec d'autres chercheurs - par une équipe de chercheurs français qui sont ou ont été membres pléniers ou associés du Centre d'analyse et de mathématique sociale (CAMS). |
| Numéro | 190, Été 2010, n° spécial Théories et usages. Numéro en hommage à Bruno Leclerc |
| Langue | Anglais |
Cette création est mise à disposition sous un contrat Creative Commons