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
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.
Hiroaki SUTO
Kyoto University
Aleksandar SHURBEVSKI
Kyoto University
Hiroshi NAGAMOCHI
Kyoto University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Hiroaki SUTO, Aleksandar SHURBEVSKI, Hiroshi NAGAMOCHI, "The Stable Roommates Problem with Unranked Entries" in IEICE TRANSACTIONS on Fundamentals,
vol. E101-A, no. 9, pp. 1412-1419, September 2018, doi: 10.1587/transfun.E101.A.1412.
Abstract: The family of stable matching problems have been well-studied across a wide field of research areas, including economics, mathematics and computer science. In general, an instance of a stable matching problem is given by a set of participants who have expressed their preferences of each other, and asks to find a “stable” matching, that is, a pairing of the participants such that no unpaired participants prefer each other to their assigned partners. In the case of the Stable Roommates Problem (SR), it is known that given an even number n of participants, there might not exist a stable matching that pairs all of the participants, but there exist efficient algorithms to determine if this is possible or not, and if it is possible, produce such a matching. Common extensions of SR allow for the participants' preference lists to be incomplete, or include indifference. Allowing indifference in turn, gives rise to different possible definitions of stability, super, strong, and weak stability. While instances asking for super and strongly stable matching can be efficiently solved even if preference lists are incomplete, the case of weak stability is NP-complete. We examine a restricted case of indifference, introducing the concept of unranked entries. For this type of instances, we show that the problem of finding a weakly stable matching remains NP-complete even if each participant has a complete preference list with at most two unranked entries, or is herself unranked for up to three other participants. On the other hand, for instances where there are m acceptable pairs and there are in total k unranked entries in all of the participants' preference lists, we propose an O(2kn2)-time and polynomial space algorithm that finds a stable matching, or determines that none exists in the given instance.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E101.A.1412/_p
Copier
@ARTICLE{e101-a_9_1412,
author={Hiroaki SUTO, Aleksandar SHURBEVSKI, Hiroshi NAGAMOCHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={The Stable Roommates Problem with Unranked Entries},
year={2018},
volume={E101-A},
number={9},
pages={1412-1419},
abstract={The family of stable matching problems have been well-studied across a wide field of research areas, including economics, mathematics and computer science. In general, an instance of a stable matching problem is given by a set of participants who have expressed their preferences of each other, and asks to find a “stable” matching, that is, a pairing of the participants such that no unpaired participants prefer each other to their assigned partners. In the case of the Stable Roommates Problem (SR), it is known that given an even number n of participants, there might not exist a stable matching that pairs all of the participants, but there exist efficient algorithms to determine if this is possible or not, and if it is possible, produce such a matching. Common extensions of SR allow for the participants' preference lists to be incomplete, or include indifference. Allowing indifference in turn, gives rise to different possible definitions of stability, super, strong, and weak stability. While instances asking for super and strongly stable matching can be efficiently solved even if preference lists are incomplete, the case of weak stability is NP-complete. We examine a restricted case of indifference, introducing the concept of unranked entries. For this type of instances, we show that the problem of finding a weakly stable matching remains NP-complete even if each participant has a complete preference list with at most two unranked entries, or is herself unranked for up to three other participants. On the other hand, for instances where there are m acceptable pairs and there are in total k unranked entries in all of the participants' preference lists, we propose an O(2kn2)-time and polynomial space algorithm that finds a stable matching, or determines that none exists in the given instance.},
keywords={},
doi={10.1587/transfun.E101.A.1412},
ISSN={1745-1337},
month={September},}
Copier
TY - JOUR
TI - The Stable Roommates Problem with Unranked Entries
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1412
EP - 1419
AU - Hiroaki SUTO
AU - Aleksandar SHURBEVSKI
AU - Hiroshi NAGAMOCHI
PY - 2018
DO - 10.1587/transfun.E101.A.1412
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E101-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2018
AB - The family of stable matching problems have been well-studied across a wide field of research areas, including economics, mathematics and computer science. In general, an instance of a stable matching problem is given by a set of participants who have expressed their preferences of each other, and asks to find a “stable” matching, that is, a pairing of the participants such that no unpaired participants prefer each other to their assigned partners. In the case of the Stable Roommates Problem (SR), it is known that given an even number n of participants, there might not exist a stable matching that pairs all of the participants, but there exist efficient algorithms to determine if this is possible or not, and if it is possible, produce such a matching. Common extensions of SR allow for the participants' preference lists to be incomplete, or include indifference. Allowing indifference in turn, gives rise to different possible definitions of stability, super, strong, and weak stability. While instances asking for super and strongly stable matching can be efficiently solved even if preference lists are incomplete, the case of weak stability is NP-complete. We examine a restricted case of indifference, introducing the concept of unranked entries. For this type of instances, we show that the problem of finding a weakly stable matching remains NP-complete even if each participant has a complete preference list with at most two unranked entries, or is herself unranked for up to three other participants. On the other hand, for instances where there are m acceptable pairs and there are in total k unranked entries in all of the participants' preference lists, we propose an O(2kn2)-time and polynomial space algorithm that finds a stable matching, or determines that none exists in the given instance.
ER -