Back to results

University of Waterloo

The Matching Augmentation Problem: A 7/4-Approximation Algorithm

Abstract

dc:description.abstract

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

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Dippel, Jack
Advisor dc:contributor.advisor
  • Cheriyan, Joseph

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/14700

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Dippel, Jack. The Matching Augmentation Problem: A 7/4-Approximation Algorithm. University of Waterloo, 2019. http://hdl.handle.net/10012/14700