Polynomial time algorithm for an optimal stable assignment with multiple partners
Polynomial time algorithm for an optimal stable assignment with multiple partners
复制标题
用于与多个伙伴进行最佳稳定分配的多项式时间算法
DOI：
10.1016/j.tcs.2007.02.050
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Varun S. Malhotra
中科院分区：
文献类型：
--
作者：
V. Bansal;Aseem Agrawal;Varun S. Malhotra
本文考虑多对多版本的稳定婚姻问题，其中每个男人和女人有一个严格的偏好排序的异性成员，他或她认为是可以接受的。此外，每个男子和妇女都希望尽可能多地与可接受的伴侣配对，以达到他或她规定的配额。在这种设置中，提供了一种多项式时间算法，用于找到一个稳定的匹配，使所有男性和女性的伴侣排名之和最小化。有人认为，这个总和可以被用来作为一个最优性标准，最小化总的不满，如果在合作伙伴组合的偏好满足无互补性条件。本文的结果扩展了已知的一对一版本的问题。
This paper considers the many-to-many version of the stable marriage problem where each man and woman has a strict preference ordering on the members of the opposite sex that he or she considers acceptable. Further, each man and woman wishes to be matched to as many acceptable partners as possible, up to his or her specified quota. In this setup, a polynomial time algorithm for finding a stable matching that minimizes the sum of partner ranks across all men and women is provided. It is argued that this sum can be used as an optimality criterion for minimizing total dissatisfaction if the preferences over partner-combinations satisfy a no-complementarities condition. The results in this paper extend those already known for the one-to-one version of the problem.