A Stable Marriages Algorithm to Optimize Satisfaction and Equity

N. Suvonvorn and B. Zavidovique, (2006), A Stable Marriages Algorithm to Optimize Satisfaction and Equity, In Proceedings of International Conference on Image Analysis and Recognition (ICIAR), September 18-20, 2006, Povoa de Varzim, Portugal, vol. 2, pp. 422- 433.

Abstract

iciar06This paper deals with designing an algorithm for feature pairing in vision, based on the “stable marriages” paradigm. Our SZ is an extension of the recently published BZ algorithm. BZ scans the so-called “marriage table” to optimize global satisfaction and equity over all couples. It still gets about 5% unstable results in average. After a case study that sorts blocking situations into 4 types, we explain here how to resolve unstability in forcing blocking pairs to marry wrt. their type. SZ is compared to BZ and Gale-Shapley on 40000 instances of a 200 persons large population. An example of stereo reconstruction by SZ is given for illustration.

Related posts: