A min-conflicts algorithm for maximum stable matchings of the hospitals/residents problem with ties
Authors: Nguyen Thi Uyen, Nguyen Long Giang, Truong-Thang Nguyen, Hoang Huu Viet
In Proceedings of the 2020 RIVF International Conference on Computing and Communication Technologies, RIVF 2020
: 1 : 1-6
Publishing year: 9/2020
This paper presents a min-conflicts algorithm to find a maximum weakly stable matching for the Hospitals/Residents problem with Ties (MAX-HRT). We represent the problem in terms of a constraint satisfaction problem and apply a local search approach to solve the problem. Our key idea is to find a set of undominated blocking pairs from residents' point of view and then remove the best one to not only reject all the blocking pairs formed by the residents but also to reject as many as possible the blocking pairs formed by hospitals from the hospitals' point of view. Experiments show that our algorithm is efficient for solving MAX-HRT of large sizes.
Heuristics. Hospitals/Residents. Min-Conflicts. Local Search. Undominated Blocking Pairs.
