Back to search

Clemson University

Batch Testing, Adaptive Algorithms, and Heuristic Applications for Stable Marriage Problems

Abstract

dc:description.abstract

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 1989 book The Stable Marriage Problem: Structure and Algorithms<\italic> on whether, given a reasonable amount of preprocessing time, stable matching solutions could be verified in less than O(n^2) time. We answer this question affirmatively, showing an algorithm that will verify k different matchings in O((m + kn) log^2 n) time. Second, we show how the concept of an adaptive algorithm can be used to speed up running time in certain cases of the stable marriage problem where the disorder present in preference lists is limited. While a problem with identical lists can be solved in a trivial O(n) running time, we present an O(n+k) time algorithm where the women have identical preference lists, and the men have preference lists that differ in k positions from a set of identical lists. We also show a visualization program for better understanding the effects of changes in preference lists. Finally, we look at preference list based matching as a heuristic for cost based matching problems. In theory, this method can lead to arbitrarily bad solutions, but through empirical testing on different types of random sources of data, we show how to obtain reasonable results in practice using methods for generating preference lists “asymmetrically” that account for long-term ramifications of short-term decisions. We also discuss several ways to measure the stability of a solution and how this might be used for bicriteria optimization approaches based on both cost and stability.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (PhD)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Computer Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Dabney, John
Contributors dc:contributor
  • Dean, Brian C
  • Jacobs , David
  • Madison , Wayne
  • Malloy , Brian

Subjects

dc:subject × 5

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_dissertations/664

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Dabney, John. Batch Testing, Adaptive Algorithms, and Heuristic Applications for Stable Marriage Problems. Dissertation thesis, https://open.clemson.edu/all_dissertations/664