An Approximation Algorithm for the Stable Marriagae Problem with Ties and Incomplete Lists

Consider the bipartite matching problem with two sets of participants: men (L) and women (R). Each person participating has a strict and complete preference list over participants from the other set. The goal is to pair men and women such that no one can improve their partner by breaking away from the centralized matching scheme. Problems that exhibit this flavor are commonly classified as ordinal matchings. Gale and Shapley showed how to obtain such a matching (otherwise known as a “stable” matching). Generalizations of this model have found relevance in several centralized matching schemes such as the National Residency Matching Program where graduating doctors are matched to hospitals, human organ transplant exchange markets, and housing allocation markets. In this thesis, we study a generalization of the stable matching problem, where the preference lists of participants are allowed to contain ties and missing entries. Here, we seek to find a stable matching of maximum cardinality. The problem was shown to be NP-hard, and is one of the most prominent problems in the domain of ordinal matching. When preference lists are restricted to one side of the problem, Iwama et al. [28] devised a variant of the famous Gale-Shapley stable matching algorithm that breaks ties using edge weights obtained by solving a linear programming relaxation of the problem, leading to an approximation ratio of 25/17 (approximately 1.47058). We apply ideas from factor-revealing LPs to show that this analysis in [28] is an upper bound, but that the algorithm and analysis can be improved to yield an approximation ratio of at most 19/13 (approximately 1.461538), improving the best currently-known approximation ratio (obtained via different techniques in [39]) of 41/28 (approximately 1.4643)