Date of Award


Document Type


Degree Name

Doctor of Philosophy (PhD)

Legacy Department

Computer Science

Committee Chair/Advisor

Dr. Brian C. Dean

Committee Member

Dr. Amy Apon

Committee Member

Dr. Ilya Safro

Committee Member

Dr. Pradip K. Srimani


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).



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.