期刊名称：International Journal of Computer Science & Information Technology (IJCSIT)
印刷版ISSN：0975-4660
电子版ISSN：0975-3826
出版年度：2016
卷号：8
期号：1
页码：75
出版社：Academy & Industry Research Collaboration Center (AIRCC)
摘要：We consider a variant of the Stable Marriage Problem where preference lists of man/woman may beincomplete, may contain ties and may have bounded length in presence of a notion of social stability. Inreal world matching applications like NRMP and Scottish medical matching scheme such restrictions canarise very frequently where set of agents (man/woman) is very large and providing a complete and strictorder preference list is practically in-feasible. In presence of ties in preference lists, there exist threedifferent notion of stability, weak stability, strong stability and super stability. The most common solution isto produce a weakly stable matching. It is a fact that in an instance of Stable Marriage problem with Tiesand Incomplete list (SMTI), weakly stable matching can have different sizes. This motivates the problem offinding a maximum cardinality weakly socially stable matching.In this paper, we find maximum size weakly socially stable matching for a special instance of StableMarriage problem with Ties and Incomplete bounded length preference list under Social Stability. Themotivation to consider this instance is the known fact, finding maximum size weakly socially stablematching in any larger instance of this problem is NP-hard.
关键词：The Stable Marriage Problem; Socially Stable Matching; Bipartite Matching; Stable Marriage Problem;with Ties and Incomplete list; Two Sided Matching; Matching under Preference.
