A Local Search Algorithm for SMTI and its extension to HRT Problems - Université Paris 1 Panthéon-Sorbonne Accéder directement au contenu
Communication Dans Un Congrès Année : 2015

A Local Search Algorithm for SMTI and its extension to HRT Problems

Résumé

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.
Fichier principal
Vignette du fichier
MATCHUP15.pdf (312.84 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01144208 , version 1 (21-04-2015)

Identifiants

  • HAL Id : hal-01144208 , version 1

Citer

Danny Munera, Daniel Diaz, Salvador Abreu, Francesca Rossi, Vijay Saraswat, et al.. A Local Search Algorithm for SMTI and its extension to HRT Problems. 3rd International Workshop on Matching Under Preferences, University of Glasgow, Apr 2015, Glasgow, United Kingdom. ⟨hal-01144208⟩
186 Consultations
325 Téléchargements

Partager

Gmail Facebook X LinkedIn More