The college admissions problem with lower and common quotas

DOI10.1016/j.tcs.2010.05.005zbMath1193.91099OpenAlexW1978256120MaRDI QIDQ986550

Robert W. Irving, David F. Manlove, Tamás Fleiner, Péter Biró

Publication date: 11 August 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://eprints.gla.ac.uk/38576/1/38576.pdf

zbMATH Keywords

NP-hardnesscollege admissions problemcommon quotaslower quotashospitals/Residents problemnested set systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Case-oriented studies in operations research (90B90) Matching models (91B68)

Related Items (46)

Simplified group activity selection with group size constraints ⋮ Strategyproof matching with regional minimum and maximum quotas ⋮ Modelling practical placement of trainee teachers to schools ⋮ Interdistrict school choice: a theory of student assignment ⋮ College admissions with stable score-limits ⋮ Stable matchings of teachers to schools ⋮ The popular matching and condensation problems under matroid constraints ⋮ Integer programming methods for special college admissions problems ⋮ Strategy-proof school choice mechanisms with minimum quotas and initial endowments ⋮ Pareto optimal matchings with lower quotas ⋮ University rankings from the revealed preferences of the applicants ⋮ The vigilant eating rule: a general approach for probabilistic economic design with constraints ⋮ Strategyproof allocation mechanisms with endowments and M-convex distributional constraints ⋮ Strategyproof mechanism for two-sided matching with resource allocation ⋮ Incomplete list setting of the hospitals/residents problem with maximally satisfying lower quotas ⋮ Refined computational complexities of hospitals/residents problem with regional caps ⋮ Cutoff stability under distributional constraints with an application to summer internship matching ⋮ Agreeable sets with matroidal constraints ⋮ Envy-freeness and relaxed stability for lower-quotas: a parameterized perspective ⋮ Refined computational complexities of hospitals/residents problem with regional caps ⋮ Matchings with lower quotas: algorithms and complexity ⋮ Finding all stable matchings with couples ⋮ A Generalized Polymatroid Approach to Stable Matchings with Lower Quotas ⋮ Matching with quorums ⋮ Stable Matching with Proportionality Constraints ⋮ Assignment Mechanisms Under Distributional Constraints ⋮ A note on the serial dictatorship with project closures ⋮ Handling preferences in student-project allocation ⋮ Graduate admission with financial support ⋮ Envy-free matchings with lower quotas ⋮ Stability concepts in matching under distributional constraints ⋮ Finding a stable matching under type-specific minimum quotas ⋮ Designing matching mechanisms under constraints: an approach from discrete convex analysis ⋮ The college admissions problem with lower and common quotas ⋮ A Matroid Approach to Stable Matchings with Lower Quotas ⋮ Envy-freeness and relaxed stability: hardness and approximation algorithms ⋮ Slot-specific priorities with capacity transfers ⋮ Envy-free matchings with one-sided preferences and matroid constraints ⋮ Stable matchings with covering constraints: a complete computational trichotomy ⋮ Unnamed Item ⋮ College admissions with ties and common quotas: integer programming approach ⋮ Dynamic reserves in matching markets ⋮ MATCHING WITH COUPLES: A MULTIDISCIPLINARY SURVEY ⋮ Unnamed Item ⋮ Popular Matchings with Lower Quotas ⋮ The hospitals/residents problem with lower quotas

Cites Work

• The college admissions problem with lower and common quotas
• Some remarks on the stable matching problem
• A tale of two mechanisms: Student placement
• Hard variants of stable marriage.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Median stable matching for college admissions
• The Geometry of Fractional Stable Matchings and Its Applications
• Stability and Polarization of Interests in Job Matching
• Conflict and Coincidence of Interest in Job Matching: Some New Results and Open Questions
• Stable marriage assignment for unequal sets
• A Fixed-Point Approach to Stable Matchings and Some Applications
• College Admissions and the Stability of Marriage
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The college admissions problem with lower and common quotas