Paper Info
Title
The College Admissions problem with lower and common quotas
Abstract
We study two generalised stable matching problems motivated by the current matching scheme used in the higher education sector in Hungary. The first problem is an extension of the College Admissions problem in which the colleges have lower quotas as well as the normal upper quotas. Here, we show that a stable matching may not exist and we prove that the problem of determining whether one does is NP-complete in general. The second problem is a different extension in which, as usual, individual colleges have upper quotas, but, in addition, certain bounded subsets of colleges have common quotas smaller than the sum of their individual quotas. Again, we show that a stable matching may not exist and the related decision problem is NP-complete. On the other hand, we prove that, when the bounded sets form a nested set system, a stable matching can be found by generalising, in non-trivial ways, both the applicant-oriented and college-oriented versions of the classical Gale-Shapley algorithm. Finally, we present an alternative view of this nested case using the concept of choice functions, and with the aid of a matroid model we establish some interesting structural results for this case.
Year
DOI
Venue
2010
10.1016/j.tcs.2010.05.005
Theor. Comput. Sci.
Keywords
DocType
Volume
Matroids,Common quotas,current matching scheme,generalised stable matching problem,Rural Hospitals theorem,Hospitals/Residents problem,stable matching,certain bounded subsets,polynomial-time algorithm,College Admissions problem,NP-hardness,related decision problem,bounded set,common quota,Nested set systems,different extension,Lower quotas,individual quota,individual college
Journal
411
Issue
ISSN
Citations 
34-36
Theoretical Computer Science
39
PageRank 
References 
Authors
1.78
7
4
Name
Order
Citations
PageRank
Péter Biró123719.83
Tamás Fleiner224127.45
Robert W. Irving31331146.76
David F. Manlove476160.45