Solving Hard Stable Matching Problems via Local Search and Cooperative Parallelization
DOI:
https://doi.org/10.1609/aaai.v29i1.9360Keywords:
Stable Matching, Parallel Local Search, Cooperative Multi-WalkAbstract
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.
Downloads
Published
2015-02-16
How to Cite
Munera, D., Diaz, D., Abreu, S., Rossi, F., Saraswat, V., & Codognet, P. (2015). Solving Hard Stable Matching Problems via Local Search and Cooperative Parallelization. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9360
Issue
Section
AAAI Technical Track: Heuristic Search and Optimization