A max-conflicts based heuristic search for the stable marriage problem with ties and incomplete lists

Hoang Huu Viet (), Nguyen Thi Uyen (), SeungGwan Lee (), TaeChoong Chung () and Le Hong Trang ()
Additional contact information
Hoang Huu Viet: Vinh University
Nguyen Thi Uyen: Vinh University
SeungGwan Lee: Kyung Hee University
TaeChoong Chung: Kyung Hee University
Le Hong Trang: Ho Chi Minh City University of Technology

Journal of Heuristics, 2021, vol. 27, issue 3, No 5, 439-458

Abstract: Abstract In this paper, we propose a heuristic search algorithm based on maximum conflicts to find a weakly stable matching of maximum size for the stable marriage problem with ties and incomplete lists. The key idea of our approach is to define a heuristic function based on the information extracted from undominated blocking pairs from the men’s point of view. By choosing a man corresponding to the maximum value of the heuristic function, we aim to not only remove all the blocking pairs formed by the man but also reject as many blocking pairs as possible for an unstable matching from the women’s point of view to obtain a solution of the problem as quickly as possible. Experiments show that our algorithm is efficient in terms of both execution time and solution quality for solving the problem.

Keywords: Adaptive search; Heuristic search; Local search; Max-conflicts; SMTI; Undominated blocking pairs (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-020-09464-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:27:y:2021:i:3:d:10.1007_s10732-020-09464-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-020-09464-8

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().