 |
Conference papers
A Local Search Algorithm for SMTI and its extension to HRT Problems
Abstract : Hospitals/Residents with Ties (HRT) forms a class of problems with many applications, some of which are of considerable size. Solving these problems has been shown to be NP-hard. In previous work, we developed a local search algorithm which displays very high performance in solving Stable Matching with Ties and Incomplete lists (SMTI) problems. In this paper, we propose a method to tackle HRT problems with a slightly modified version of our SMTI solver. We describe our method and provide an initial performance assessment, which turns out to show that the resulting solver can deal with significant HRT problems, providing optimal solutions in most cases, in a very short time.
Cited literature [21 references]
https://hal-paris1.archives-ouvertes.fr/hal-01144208
Contributor : Danny Munera <>
Submitted on : Tuesday, April 21, 2015 - 11:18:48 AM
Last modification on : Tuesday, January 19, 2021 - 11:08:39 AM
Long-term archiving on: : Wednesday, April 19, 2017 - 1:15:23 AM
Contributor : Danny Munera <>
Submitted on : Tuesday, April 21, 2015 - 11:18:48 AM
Last modification on : Tuesday, January 19, 2021 - 11:08:39 AM
Long-term archiving on: : Wednesday, April 19, 2017 - 1:15:23 AM
File
MATCHUP15.pdf
Files produced by the author(s)