Refined computational complexities of hospitals/residents problem with regional caps

DOI10.1016/j.tcs.2024.114389MaRDI QIDQ6201324

Shuichi Miyazaki, Koki Hamada

Publication date: 20 February 2024

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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
• A simplified NP-complete satisfiability problem
• 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
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures
• 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