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
안정적 매칭 문제 계열은 경제학, 수학, 컴퓨터 과학을 포함한 광범위한 연구 분야에서 잘 연구되어 왔습니다. 일반적으로 안정적인 매칭 문제의 예는 서로의 선호도를 표현한 참가자 집합에 의해 제공되며 "안정적인" 매칭, 즉 페어링되지 않은 참가자가 선호하지 않는 참가자 페어링을 찾도록 요청합니다. 지정된 파트너에게 서로. SR(Stable Roommates Problem)의 경우 짝수가 주어지는 것으로 알려져 있다. n 참가자 중에는 모든 참가자를 쌍으로 연결하는 안정적인 매칭이 없을 수도 있지만 이것이 가능한지 여부를 결정하고 가능하다면 그러한 매칭을 생성하는 효율적인 알고리즘이 있습니다. SR의 일반적인 확장은 참가자의 선호 목록이 불완전하거나 무관심을 포함하도록 허용합니다. 무관심을 허용하면 안정성, 즉 초안정성, 강함, 약한 안정성에 대한 다양한 정의가 생성됩니다. 매우 안정적이고 강력한 매칭을 요구하는 인스턴스는 선호도 목록이 불완전하더라도 효율적으로 해결할 수 있는 반면, 약한 안정성의 경우는 NP-완전입니다. 우리는 무관심의 제한된 사례를 조사하여 다음과 같은 개념을 도입합니다. 순위 없는 항목. 이러한 유형의 사례에 대해 우리는 각 참가자가 최대 2개의 순위가 지정되지 않은 항목이 있는 완전한 선호 목록을 가지고 있거나 최대 3명의 다른 참가자에 대해 순위가 지정되지 않은 경우에도 약하게 안정적인 일치를 찾는 문제가 NP-완전 상태로 유지된다는 것을 보여줍니다. 반면에 다음과 같은 경우가 있습니다. m 허용되는 쌍이 있고 전체적으로 k 모든 참가자의 선호 목록에서 순위가 지정되지 않은 항목을 제안합니다. O(2kn2)-안정적인 일치를 찾거나 주어진 인스턴스에 아무것도 존재하지 않는다고 결정하는 시간 및 다항식 공간 알고리즘입니다.
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.
부
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
부
@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},}
부
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 -