N. Suvonvorn and B. Zavidovique, (2009), Globally Satisfying and Equitable Stable Marriages and Their Complexity, International Journal of Pure and Applied Mathematics (IJPAM), 2009, Volume: 53, Issue: 3, page(s): 439-466, ISSN: 1311-8080.
Abstract
This paper deals with designing algorithms based on the ”stable marriages” paradigm, for them to take additional constraints into account. First algorithms scan the so-called ”marriage table” to optimize ”global satisfaction” and ”equity” over all cou- ples. Then, we introduce an hybrid version between the Gale-Shappley classical al-gorithm and ours. Results on thousands of populations, up to 200 person large, are systematically evaluated. These algorithms progressively improve both satisfaction and equity but they do not guarantee complete stability. Thus, the BZ algorithm is made to blow blockages out. It still produces about 5% instable results in average. After a case study that sorts blocking situations into 4 types, we explain how to resolve instability in forcing blocking pairs to marry wrt. their type. The resulting S-procedure applies after every previous algorithm, and results are systematically compared to Gale-Shapley’s on 1000 instances of a 200-person-large population. In conclusion, comparative examples of respective matching results from the al- gorithms are given for illustration of possible applications to registration, stereo reconstruction or motion finding.