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.
Cite
Text
Munera et al. "Solving Hard Stable Matching Problems via Local Search and Cooperative Parallelization." AAAI Conference on Artificial Intelligence, 2015. doi:10.1609/AAAI.V29I1.9360Markdown
[Munera et al. "Solving Hard Stable Matching Problems via Local Search and Cooperative Parallelization." AAAI Conference on Artificial Intelligence, 2015.](https://mlanthology.org/aaai/2015/munera2015aaai-solving/) doi:10.1609/AAAI.V29I1.9360BibTeX
@inproceedings{munera2015aaai-solving,
title = {{Solving Hard Stable Matching Problems via Local Search and Cooperative Parallelization}},
author = {Munera, Danny and Diaz, Daniel and Abreu, Salvador and Rossi, Francesca and Saraswat, Vijay A. and Codognet, Philippe},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2015},
pages = {1212-1218},
doi = {10.1609/AAAI.V29I1.9360},
url = {https://mlanthology.org/aaai/2015/munera2015aaai-solving/}
}