Result: Polynomial time algorithm for an optimal stable assignment with multiple partners

Title:
Polynomial time algorithm for an optimal stable assignment with multiple partners
Authors:
BANSAL, Vipul, AGRAWAL, Aseem, MALHOTRA, Varun S
Source:
Automata, languages and programming (ICALP 2003)Theoretical computer science. 379(3):317-328
Publisher Information:
Amsterdam: Elsevier, 2007.
Publication Year:
2007
Physical Description:
print, 21 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Divers, Miscellaneous, Assignation, Assignment, Asignación, Critère optimalité, Optimality criterion, Criterio optimalidad, Informatique théorique, Computer theory, Informática teórica, Mariage, Marriage, Matrimonio, Polynôme, Polynomial, Polinomio, Principe de complémentarité, Complementarity, Préférence, Preference, Preferencia, Rang, Rank, Rango, Relation ordre, Ordering, Relación orden, Rotation, Rotación, Satisfaction, Satisfacción, Temps polynomial, Polynomial time, Tiempo polinomial, 68Wxx, Algorithme polynomial, Problème mariage stable, Dis-satisfaction score, Multiple partners, Optimal assignment, Stable marriage, Substitutes, meta-rotation
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Adobe Systems, I-1A Sector 25A, Noida 201301, India
Citigroup Global Markets, 3 Temasek Avenue, Singapore 039190, Singapore
Oracle Corporation, Redwood Shores, CA 94065, United States
ISSN:
0304-3975
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=18821595
Rights:
Copyright 2008 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.18821595
Database:
PASCAL Archive

Further Information

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.