The hospitals/residents problem with lower quotas

DOI10.1007/s00453-014-9951-zzbMath1336.68098OpenAlexW1992568705MaRDI QIDQ261379

Kazuo Iwama, Shuichi Miyazaki, Koki Hamada

Publication date: 23 March 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2433/226943

zbMATH Keywords

approximation algorithmstable marriage problemstable matchinghospitals/residents problem

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Matching models (91B68)

Related Items (20)

Pareto optimal matchings with lower quotas ⋮ Two problems in max-size popular matchings ⋮ 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 ⋮ Envy-freeness and relaxed stability for lower-quotas: a parameterized perspective ⋮ Refined computational complexities of hospitals/residents problem with regional caps ⋮ Popular critical matchings in the many-to-many setting ⋮ ``Almost-stable matchings in the hospitals/residents problem with couples ⋮ Matchings with lower quotas: algorithms and complexity ⋮ A Generalized Polymatroid Approach to Stable Matchings with Lower Quotas ⋮ Assignment Mechanisms Under Distributional Constraints ⋮ Envy-free matchings with lower quotas ⋮ A Matroid Approach to Stable Matchings with Lower Quotas ⋮ Envy-freeness and relaxed stability: hardness and approximation algorithms ⋮ Stable matchings with covering constraints: a complete computational trichotomy ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Popular Matchings with Lower Quotas ⋮ How Good Are Popular Matchings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Two algorithms for the student-project allocation problem
• Size versus stability in the marriage problem
• Keeping partners together: Algorithmic results for the hospitals/residents problem with couples
• The college admissions problem with lower and common quotas
• An improved approximation lower bound for finding almost stable maximum matchings
• The stable marriage problem with master preference lists
• Some remarks on the stable matching problem
• On-line algorithms for weighted bipartite matching and stable marriages
• Stable matchings with couples
• Detecting high log-densities
• The Hospitals/Residents Problem with Quota Lower Bounds
• Gale-Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications
• NP-complete stable matching problems
• Relations between average case complexity and approximation complexity
• Improved approximation results for the stable marriage problem
• A Stab at Approximating Minimum Subadditive Join
• Greedily Finding a Dense Subgraph
• Approximation and Online Algorithms
• College Admissions and the Stability of Marriage
• The dense \(k\)-subgraph problem

This page was built for publication: The hospitals/residents problem with lower quotas