Computer Science – Artificial Intelligence
Scientific paper
2010-07-05
Computer Science
Artificial Intelligence
12 pages, Proc. PRICAI 2010 (11th Pacific Rim International Conference on Artificial Intelligence), Byoung-Tak Zhang and Mehme
Scientific paper
The stable marriage problem has a wide variety of practical applications, ranging from matching resident doctors to hospitals, to matching students to schools, or more generally to any two-sided market. We consider a useful variation of the stable marriage problem, where the men and women express their preferences using a preference list with ties over a subset of the members of the other sex. Matchings are permitted only with people who appear in these preference lists. In this setting, we study the problem of finding a stable matching that marries as many people as possible. Stability is an envy-free notion: no man and woman who are not married to each other would both prefer each other to their partners or to being single. This problem is NP-hard. We tackle this problem using local search, exploiting properties of the problem to reduce the size of the neighborhood and to make local moves efficiently. Experimental results show that this approach is able to solve large problems, quickly returning stable matchings of large and often optimal size.
Gelain Mirco
Pini Maria Silvia
Rossi Francesca
Venable Kristen Brent
Walsh Toby
No associations
LandOfFree
Local search for stable marriage problems with ties and incomplete lists does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Local search for stable marriage problems with ties and incomplete lists, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Local search for stable marriage problems with ties and incomplete lists will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-594643