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

Danny Munera 1 Daniel Diaz 1 Salvador Abreu 2 Francesca Rossi 3 Vijay Saraswat 4 Philippe Codognet 5, 6
1 CRI - Centre de Recherche en Informatique de Paris 1
2 Universidade de Évora
3 Universita degli Studi di Padova
4 IBM Thomas J. Watson Research Center
5 JFLI - Japanese French Laboratory for Informatics
6 UPMC - Université Pierre et Marie Curie - Paris 6
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.
Type de document :
Communication dans un congrès
3rd International Workshop on Matching Under Preferences, Apr 2015, Glasgow, United Kingdom. 2015
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger
https://hal-paris1.archives-ouvertes.fr/hal-01144208
Contributeur : Danny Munera <>
Soumis le : mardi 21 avril 2015 - 11:18:48
Dernière modification le : jeudi 14 juin 2018 - 10:54:02
Document(s) archivé(s) le : mercredi 19 avril 2017 - 01:15:23

Fichier

MATCHUP15.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01144208, version 1

Collections

UNIV-PARIS1 | UPMC | CRI

Citation

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, Apr 2015, Glasgow, United Kingdom. 2015. 〈hal-01144208〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

183

Téléchargements de fichiers

168

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD