University of Waterloo
The Matching Augmentation Problem: A 7/4-Approximation Algorithm
Abstract
dc:description.abstractWe 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 × 4Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/14700