Complexity of the sex-equal stable marriage problem
Complexity of the sex-equal stable marriage problem
复制标题
性别平等稳定婚姻问题的复杂性
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
A. Kato
中科院分区：
文献类型：
--
作者：
A. Kato
一个大规模的稳定婚姻问题涉及到男性和女性，每个人对所有异性成员都有严格的偏好顺序。一种称为稳定匹配的解决方案可以将男性和女性进行匹配，这样就不会出现男性和女性都更喜欢对方而不是各自的伴侣的情况。 Gusfield 和 Irving [5] 提出的性别平等稳定婚姻问题是寻找稳定匹配，其性质是男性得分之和尽可能接近女性得分之和。本文表明，即使每个人的得分与其排名一致，性别平等的稳定婚姻问题也是 NP 困难的。
A stable marriage problem of sizen involvesn men andn women each with a strict preference ordering over all the members of the opposite sex. A solution, called a stable matching, matches the men and women so that no man and woman both prefer each other to their respective partners. The sex-equal stable marriage problem posed by Gusfield and Irving [5] is that of finding a stable matching with the property that the sum of the men’s scores is as close as possible to that of the women’s. This paper shows that the sex-equal stable marriage problem is NP-hard even if each person’s scores coincide with his rankings.