|
Title:
|
A FRAMEWORK FOR SOLVING HARD VARIANTS OF STABLE MATCHING WITHIN A LIMITED TIME |
|
Author(s):
|
Tarmo Veskioja , Leo Võhandu |
|
ISBN:
|
972-98947-3-6 |
|
Editors:
|
Nuno Guimarães and Pedro Isaías |
|
Year:
|
2004 |
|
Edition:
|
Single |
|
Keywords:
|
Stable matching, genetic algorithm, monotone systems, core, majority assignment. |
|
Type:
|
Short Paper |
|
First Page:
|
2177 |
|
Last Page:
|
2182 |
|
Language:
|
English |
|
Cover:
|
|
|
Full Contents:
|
click to dowload 
|
|
Paper Abstract:
|
In the original stable marriage problem all the participants have to rank all members of the opposite party. Two variations for this problem allow for incomplete preference lists and ties in preferences. Most of the real-world matching problems allow for both types of relaxations. Finding a maximum cardinality solution for the stable matching problem with both ties and incomplete lists (SMTI) is NP-Complete and even the approximation is APX-hard. Finding an egalitarian solution for SMTI is also NP-Complete and APX-hard. If members from one side are allowed to form couples and submit combined preferences, then the set of stable matchings may be empty and determining if a market has any stable matchings is NP-Complete. Real-world applications of centralized matching need to provide a solution within a limited time. We propose a matching framework that always gives a solution. It is based on a genetic algorithm that uses intermediate or approximate solutions from other matching algorithms. We also give a broader definition for the core of marriage game, when the set of stable matchings is empty and it is necessary to use majority voting between matchings in a tournament. We use monotone systems based approach for tournament selection. |
|
|
|
|
|
|
