La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

The Stable Roommates Problem with Unranked Entries Le problème des colocataires stables avec les entrées non classées

Hiroaki SUTO, Aleksandar SHURBEVSKI, Hiroshi NAGAMOCHI

  • Vues en texte intégral

    0

  • Citer

Résumé:

La famille des problèmes d’appariement stable a été bien étudiée dans un large domaine de domaines de recherche, notamment l’économie, les mathématiques et l’informatique. En général, un exemple de problème d'appariement stable est donné par un ensemble de participants qui ont exprimé leurs préférences les uns envers les autres, et demande de trouver un appariement « stable », c'est-à-dire un appariement de participants tel qu'aucun participant non apparié ne préfère les uns les autres avec leurs partenaires assignés. Dans le cas du problème des colocataires stables (SR), on sait que étant donné un nombre pair n des participants, il n’existe peut-être pas d’appariement stable qui associe tous les participants, mais il existe des algorithmes efficaces pour déterminer si cela est possible ou non, et si c’est possible, produire un tel appariement. Les extensions courantes de SR permettent que les listes de préférences des participants soient incomplètes ou incluent l'indifférence. Permettre l’indifférence à son tour donne lieu à différentes définitions possibles de la stabilité, super, forte et faible stabilité. Alors que les instances demandant une correspondance super et fortement stable peuvent être résolues efficacement même si les listes de préférences sont incomplètes, le cas de faible stabilité est NP-complet. Nous examinons un cas restreint d'indifférence, en introduisant le concept de non classé entrées. Pour ce type de cas, nous montrons que le problème de trouver une correspondance faiblement stable reste NP-complet même si chaque participant a une liste de préférences complète avec au plus deux entrées non classées, ou est lui-même non classé pour jusqu'à trois autres participants. En revanche, dans les cas où il y a m paires acceptables et il y en a au total k entrées non classées dans toutes les listes de préférences des participants, nous proposons un O(2kn2)-algorithme de temps et d'espace polynomial qui trouve une correspondance stable ou détermine qu'il n'en existe pas dans l'instance donnée.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.9 pp.1412-1419
Date de publication
2018/09/01
Publicisé
ISSN en ligne
1745-1337
DOI
10.1587/transfun.E101.A.1412
Type de manuscrit
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Catégories

Auteurs

Hiroaki SUTO
  Kyoto University
Aleksandar SHURBEVSKI
  Kyoto University
Hiroshi NAGAMOCHI
  Kyoto University

Mots-clés

Table des matières