Integer programming methods for special college admissions problems

DOI10.1007/S10878-016-0085-XzbMATH Open1356.90119arXiv1408.6878OpenAlexW2167798820MaRDI QIDQ346530FDOQ346530

Authors: Kolos Csaba Ágoston, Péter Biró, Iain McBride 

Publication date: 29 November 2016

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Abstract: We develop Integer Programming (IP) solutions for some special college admission problems arising from the Hungarian higher education admission scheme. We focus on four special features, namely the solution concept of stable score-limits, the presence of lower and common quotas, and paired applications. We note that each of the latter three special feature makes the college admissions problem NP-hard to solve. Currently, a heuristic based on the Gale-Shapley algorithm is being used in the application. The IP methods that we propose are not only interesting theoretically, but may also serve as an alternative solution concept for this practical application, and also for other ones.

Full work available at URL: https://arxiv.org/abs/1408.6878

Recommendations

• Integer programming methods for special college admissions problems
• Integer programming techniques for college admission problem with common quotas
• College admissions with ties and common quotas: integer programming approach
• The college admissions problem with lower and common quotas
• College admissions with stable score-limits

zbMATH Keywords

simulationsinteger programmingcollege admissions problemcommon quotaslower quotaspaired applicationsstable score-limits

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Integer programming (90C10)

Cites Work

• Some remarks on the stable matching problem
• NP-complete stable matching problems
• College Admissions and the Stability of Marriage
• Keeping partners together: Algorithmic results for the hospitals/residents problem with couples
• The college admissions problem with lower and common quotas
• On the stable \(b\)-matching polytope.
• Many-to-One Stable Matching: Geometry and Fairness
• Choice function-based two-sided markets: stability, lattice property, path independence and algorithms
• Matching with couples: a multidisciplinary survey
• College admissions with stable score-limits
• Stable matching with couples: an empirical study
• The stable admissions polytope
• Stable Matchings, Optimal Assignments, and Linear Programming
• Stable matching problems with exchange restrictions
• Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
• Characterization of stable matchings as extreme points of a polytope
• Integer programming methods for special college admissions problems
• Backward unraveling over time: The evolution of strategic behavior in the entry level British medical labor markets

Cited In (17)

• Stable fractional matchings
• A nonlinear goal programming model for university admission capacity planning with modified differential evolution algorithm
• The singleton core in the college admissions problem and its application to the national resident matching program (NRMP)
• College admissions with ties and common quotas: integer programming approach
• Stable matching: An integer programming approach
• Complexity of finding Pareto-efficient allocations of highest welfare
• Integer programming methods for special college admissions problems
• The sorting hat goes to college
• Stability Representations of Many-to-One Matching Problems: An Integer Optimization Approach
• Integer programming techniques for college admission problem with common quotas
• Online voluntary mentoring: optimising the assignment of students and mentors
• University rankings from the revealed preferences of the applicants
• Optimization methods and algorithms
• Cutoff stability under distributional constraints with an application to summer internship matching
• Review of the theory of stable matchings and contract systems
• Mathematical models for stable matching problems with ties and incomplete lists
• Novel integer programming models for the stable kidney exchange problem

This page was built for publication: Integer programming methods for special college admissions problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q346530)