The stable marriage problem, displayed at the Symposium on Discrete Algorithms (SODA), which was held in New Orleans in January, 2007, is presented. The problem involves different sets of men and women, providing a rank-ordered preference list of members of the opposite sex. The aim of the problem is to find a matching, which eliminates blocking pairs. The paper presented by Iwama presents a generalization of the basic problem, where the preference list may have ties and include members of the opposite sex. The model says that finding a stable marriage without blocking pairs with the largest cardinality is NP-Complete. It was also observed that a local improvement-based approach offers an approximation factor of 1.8. The case, which presents G as a bipartite graph is known as Open shop Scheduling.
ASJC Scopus subject areas
- Mathematics (miscellaneous)