Paper Info
Title
A matroid approach to stable matchings with lower quotas
Abstract
In SODA'10, Huang introduced the laminar classified stable matching problem (LCSM for short) that is motivated by academic hiring. This problem is an extension of the well-known hospitals/residents problem in which a hospital has laminar classes of residents and it sets lower and upper bounds on the number of residents that it would hire in that class. Against the intuition that stable matching problems with lower quotas are difficult in general, Huang proved that this problem can be solved in polynomial time. In this paper, we propose a matroid-based approach to this problem and we obtain the following results. (i) We solve a generalization of the LCSM problem. (ii) We exhibit a polyhedral description for stable assignments of the LCSM problem, which gives a positive answer to Huang's question. (iii) We prove that the set of stable assignments of the LCSM problem has a lattice structure similarly to the ordinary stable matching model.
Year
DOI
Venue
2012
10.1287/moor.2015.0751
Math. Oper. Res.
Keywords
Field
DocType
laminar class,stable matching problem,classified stable matching problem,stable assignment,following result,lower quota,academic hiring,lcsm problem,residents problem,stable matchings,matroid approach,ordinary stable matching model
Stable roommates problem,Matroid,Discrete mathematics,Combinatorics,Stable marriage problem,Intuition,Time complexity,Mathematics
Conference
Volume
Issue
ISSN
41
2
0364-765X
Citations 
PageRank 
References 
4
0.54
9
Authors
2
Name
Order
Citations
PageRank
Tamás Fleiner124127.45
Naoyuki Kamiyama28023.40