A Parallel Approach to the Stable Marriage Problem

This paper describes two parallel algorithms for the stable marriage problem implemented on a MIMD parallel computer. The algorithms are tested against sequential algorithms on randomly generated and worst-case instances. The results clearly show that the combination fo a very simple problem and a commercial MIMD system results in parallel algorithms which are not competitive with sequential algorithms wrt. practical performance. 1 Introduction In 1962 the Stable Marriage Problem was introduced by David Gale and Lloyd Shapley in a paper entitled "College Admissions and the Stability of Marriage". Informally, a stable marriage is a one-to-one matching of a set of men to a set of women, such that for any pair of a man and a woman, not both prefer the other to their assigned partner. This paper describes the development of two parallel algorithms for the stable marriage problem. In section 2 the basic concepts of the stable marriage problem are introduced. In section 3 two sequential al..