A min-conflicts algorithm for maximum stable matchings of the hospitals/residents problem with ties

Autor:	Hoang Huu Viet, Nguyen Long Giang, Truong-Thang Nguyen, Nguyen Thi Uyen
Rok vydání:	2020
Předmět:	Mathematical optimization Matching (graph theory) Computer science Key (cryptography) Heuristics Set (psychology) Blocking (statistics) Min-conflicts algorithm Constraint satisfaction problem Local search (constraint satisfaction)
Zdroj:	RIVF
DOI:	10.1109/rivf48685.2020.9140756
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::aa043698906b8735682fdda686ef6e2a https://doi.org/10.1109/rivf48685.2020.9140756 Zobrazit plný text záznamu