초록 안정적인 룸메이트 문제(SRI)의 안정적인 매칭의 존재는 불완전한 선호 목록이 있는 경우에도 다항 시간 내에 결정할 수 있지만, 일부 공정성 기준을 가진 SRI 문제는 해결할 수 없습니다. 안정적인 매칭이 존재하는 경우 에이전트의 총 만족도를 극대화하려는 평등주의 SRI는 SRI의 어려운 변형 중 하나입니다. 이러한 어려운 변형의 SRI를 해결하기 위한 방법들의 실험적 평가를 위해 여러 잘 알려진 알고리즘이 무작위 벤치마크 인스턴스를 생성하는 데 사용되었습니다. 그러나 이러한 벤치마크 인스턴스는 항상 만족스럽지 않으며, 존재하는 안정적인 매칭이 있을 경우 일반적으로 안정적인 매칭의 수가 적습니다. 이러한 SRI 인스턴스의 경우, 평등주의 SRI의 NP-hard 성에도 불구하고 모든 안정적인 매칭을 열거하여 평등한 안정적인 매칭을 찾는 것은 실용적입니다. 본 연구에서는 매우 많은 솔루션을 갖고 있으며 모든 안정적인 매칭을 열거함으로써 평등한 안정적인 매칭을 찾기 어려운 SRI에 대한 벤치마크 인스턴스를 생성하는 새로운 알고리즘을 소개합니다.
Yilmaz et al. (수,)은 이 질문을 연구했습니다.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: