Back to results

Clemson University

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

Abstract

dc:description.abstract

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

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
  • Jalasutram, Rommel
Contributors dc:contributor
  • Dr. Brian C. Dean
  • Dr. Amy Apon
  • Dr. Ilya Safro
  • Dr. Pradip K. Srimani

Subjects

dc:subject × 1

Identifiers

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

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

Jalasutram, Rommel. An Approximation Algorithm for the Stable Marriagae Problem with Ties and Incomplete Lists. Dissertation thesis, https://open.clemson.edu/all_dissertations/1615