Solving Hard Stable Matching Problems via Local Search and Cooperative Parallelization

Abstract : Stable matching problems have several practical applications. If preference lists are truncated and contain ties, finding a stable matching with maximal size is computationally difficult. We address this problem using a local search technique, based on Adaptive Search and present experimental evidence that this approach is much more efficient than state-of-the-art exact and approximate methods. Moreover, parallel versions (particularly versions with communication) improve performance so much that very large and hard instances can be solved quickly.
Type de document :
Communication dans un congrès
29th AAAI Conference on Artificial Intelligence, Jan 2015, Austin, TX, United States
Liste complète des métadonnées


https://hal-paris1.archives-ouvertes.fr/hal-01144214
Contributeur : Danny Munera <>
Soumis le : mardi 21 avril 2015 - 11:25:59
Dernière modification le : mercredi 22 avril 2015 - 01:05:26
Document(s) archivé(s) le : mercredi 19 avril 2017 - 01:12:18

Fichier

SMTI-AAAI15-NC.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01144214, version 1

Collections

Citation

Danny Munera, Daniel Diaz, Salvador Abreu, Francesca Rossi, Vijay Saraswat, et al.. Solving Hard Stable Matching Problems via Local Search and Cooperative Parallelization. 29th AAAI Conference on Artificial Intelligence, Jan 2015, Austin, TX, United States. <hal-01144214>

Partager

Métriques

Consultations de
la notice

165

Téléchargements du document

157