Physical Sciences and Mathematics Commons^™

Batch Testing, Adaptive Algorithms, And Heuristic Applications For Stable Marriage Problems, John Dabney

All Dissertations

In this dissertation we focus on different variations of the stable matching (marriage) problem, initially posed by Gale and Shapley in 1962. In this problem, preference lists are used to match n men with n women in such a way that no (man, woman) pair exists that would both prefer each other over their current partners. These two would be considered a blocking pair, preventing a matching from being considered stable. In our research, we study three different versions of this problem.
First, we consider batch testing of stable marriage solutions. Gusfield and Irving presented an open problem in their …