<?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-22T09:28:13Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/14700" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/14700</identifier><datestamp>2025-03-26T23:32:40Z</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">Cheriyan, Joseph</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="cc7d2cab-32bf-499d-a37a-067d66db6976" confidence="600">Dippel, Jack</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2019-05-23T18:15:21Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2019-05-23T18:15:21Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2019-05-23</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2019-05-10</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/14700</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">We present a 7/4 approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost. We first present a series of approximation guarantee preserving reductions, each of which can be performed in polytime. Performing these reductions gives us a restricted collection of MAP instances.&#xd;
We present a 7/4 approximation algorithm for this restricted set of MAP instances. The algorithm starts with a subgraph which is a min-cost 2-edge cover, contracts its blocks, adds paths to the subgraph to cover all its bridges, and finally adds cycles to the subgraph to connect all its components. We contract any blocks created throughout. The algorithm ends when the subgraph is a single vertex, and we output all the edges we’ve contracted which form a 2ECSS.</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">map</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">matching augmentation problem</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">approximation algorithm</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">7/4</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">The Matching Augmentation Problem: A 7/4-Approximation Algorithm</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">Cheriyan, Joseph</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>