A GENERALIZATION OF THE STABLE MATCHING PROBLEM
檔案
- A1995QV73800008.pdf (1.04 MB, Adobe PDF)
日期
1995-04-21
類型
期刊名稱
DISCRETE APPLIED MATHEMATICS
卷期與頁次
第 59 卷第 1 期,頁 87–102
ISSN
0166-218X
語言
英文
摘要
It is known that there may not exist any stable matching for a given instance of the stable roommates problem. A stable partition is a structure that generalizes the notion of a stable matching; Tan (1991) proved that every instance of the stable roommates problem contains at least one such structure. In this paper we propose a new algorithm for finding a stable partition, and hence a new algorithm for finding a stable matching if one exists. Our algorithm processes the problem dynamically as long as certain relative preference orders are maintained. Some theoretical results about stable partitions are also presented.