Refined computational complexities of hospitals/residents problem with regional caps

DOI10.1007/978-3-031-22105-7_30arXiv2107.03123OpenAlexW3182734732MaRDI QIDQ6113860

Shuichi Miyazaki, Koki Hamada

Publication date: 10 August 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityNP-completenesspolynomial-time algorithmstrong stabilitystable matchinghospitals/residents problemregional cap

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Related Items (2)

Refined computational complexities of hospitals/residents problem with regional caps ⋮ Refined computational complexities of hospitals/residents problem with regional caps

Cites Work

• Unnamed Item
• The hospitals/residents problem with lower quotas
• Strategyproof matching with regional minimum and maximum quotas
• Stability concepts in matching under distributional constraints
• The college admissions problem with lower and common quotas
• Some remarks on the stable matching problem
• Envy-free matchings with lower quotas
• Stability and strategy-proofness for matching with constraints: A necessary and sufficient condition
• Popular Matchings with Lower Quotas
• College Admissions and the Stability of Marriage
• Envy-freeness and relaxed stability: hardness and approximation algorithms
• Refined computational complexities of hospitals/residents problem with regional caps

This page was built for publication: Refined computational complexities of hospitals/residents problem with regional caps