검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

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 순위가 지정되지 않은 항목의 안정적인 룸메이트 문제

Hiroaki SUTO, Aleksandar SHURBEVSKI, Hiroshi NAGAMOCHI

  • 조회수

    0

  • 이것을 인용

요약 :

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

발행
IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.9 pp.1412-1419
발행일
2018/09/01
공개일
온라인 ISSN
1745-1337
DOI
10.1587/transfun.E101.A.1412
원고의 종류
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
범주

작성자

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

키워드