Refined computational complexities of Hospitals/Residents problem with regional caps

The Hospitals/Residents problem (HR) is a many-to-one matching problem whose solution concept is stability. It is widely used in assignment systems such as assigning medical students (residents) to hospitals. To resolve imbalance in the number of residents assigned to hospitals, an extension called...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2024-03, Vol.989, p.114389, Article 114389
Main Authors: Hamada, Koki, Miyazaki, Shuichi
Format: Article
Language:English
Subjects:
Computational complexity
Hospitals/Residents problem
NP-completeness
Polynomial-time algorithm
Regional cap
Stable matching
Strong stability
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Hospitals/Residents problem (HR) is a many-to-one matching problem whose solution concept is stability. It is widely used in assignment systems such as assigning medical students (residents) to hospitals. To resolve imbalance in the number of residents assigned to hospitals, an extension called HR with regional caps (HRRC) was introduced. In this problem, a positive integer (called a regional cap) is associated with a subset of hospitals (called a region), and the total number of residents assigned to hospitals in a region must be at most its regional cap. Kamada and Kojima [1,2] defined strong stability for HRRC and demonstrated that a strongly stable matching does not necessarily exist. Recently, Aziz et al. [3] proved that the problem of determining if a strongly stable matching exists is NP-complete in general. In this paper, we refine Aziz et al.'s result by investigating the computational complexity of the problem in terms of the length of preference lists, the size of regions, and whether or not regions can overlap, and completely classify tractable and intractable cases.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2024.114389