Polynomial time algorithm for an optimal stable assignment with multiple partners

被引：21

作者：

Bansal, Vipul

Agrawal, Aseem

Malhotra, Varun S.

机构：

[1] Adobe Syst, Noida 201301, India

[2] Oracle Corp, Redwood Shores, CA 94065 USA

[3] Citigrp Global Markets, Singapore 039190, Singapore

来源：

THEORETICAL COMPUTER SCIENCE | 2007年 / 379卷 / 03期

关键词：

stable marriage; multiple partners; optimal assignment; substitutes; dis-satisfaction score; meta-rotation;

D O I：

10.1016/j.tcs.2007.02.050

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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. (c) 2007 Elsevier B.V. All rights reserved.

引用

页码：317 / 328

页数：12