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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download
https://hal-paris1.archives-ouvertes.fr/hal-01144208
Contributor : Danny Munera <>
Submitted on : Tuesday, April 21, 2015 - 11:18:48 AM
Last modification on : Friday, September 27, 2019 - 12:16:04 PM
Long-term archiving on : Wednesday, April 19, 2017 - 1:15:23 AM

File

MATCHUP15.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01144208, version 1

Collections

UNIV-PARIS1 | UPMC | CRI | SORBONNE-UNIVERSITE | SU-SCIENCES | UMI-3527

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, University of Glasgow, Apr 2015, Glasgow, United Kingdom. ⟨hal-01144208⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

226

Files downloads

250

Contact

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