<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T20:17:46Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/16052" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/16052</identifier><datestamp>2025-03-26T23:35:47Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9928</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Koenemann, Jochen</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="f1a90aa3-68a3-4831-94a3-472fcb1768d9" confidence="600">Tofigzade, Natig</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2020-07-10T17:15:30Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2020-07-10T17:15:30Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2020-07-10</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2020-06-25</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/16052</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">In the stable matching problem we are given a bipartite graph G = (A ∪ B, E) where A and B represent disjoint groups of agents, each of whom has ordinal preferences over the members of the opposite group. The goal is to find an assignment of agents in one group to those in the other such that no pair of agents prefer each other to their assignees.&#xd;
In this thesis we study the stable matching problem with ties and incomplete preferences. If agents are allowed to have ties and incomplete preferences, computing a stable matching of maximum cardinality is known to be NP-hard. Furthermore, it is known to be NP-hard to achieve a performance guarantee of 33/29 − ε (≈ 1.1379) and UGC-hard to attain that of 4/3 − ε (≈ 1.3333). We present a polynomial-time approximation algorithm with a performance guarantee of (3L − 2)/(2L − 1) where L is the maximum tie length. Our result matches the known lower bound on the integrality gap for the associated LP formulation.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Combinatorial Optimization</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Stable Matching</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Algorithmic Game Theory</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">An Algorithm for Stable Matching with Approximation up to the Integrality Gap</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Koenemann, Jochen</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1" lang="en">Faculty of Mathematics</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>