dc.rights.license | CC-BY-NC-ND | |

dc.contributor.advisor | Bisseling, Rob | |

dc.contributor.author | Best, David de | |

dc.date.accessioned | 2023-07-01T01:01:22Z | |

dc.date.available | 2023-07-01T01:01:22Z | |

dc.date.issued | 2023 | |

dc.identifier.uri | https://studenttheses.uu.nl/handle/20.500.12932/44078 | |

dc.description.abstract | The maximum weight matching problem is a well-studied and central problem in graph theory, for which a variety of exact and approximation algorithms exist. Parallelisation of these algorithms is often hard, as it is for many graph problems. By designing an algorithm using the GraphBLAS standard, we gain easy access to parallelism in executing the sparse matrix operations that constitute the solution procedure.
We propose an approximation algorithm based on searching and applying a set of positive-gain k-augmentations. In this method, searching for sets of 1-, 2- and 3-augmentations can be performed in linear time in terms of the size of the input graph. By performing a series of these searches and applying the positive-gain augmentations until none are available, we can guarantee a 3/4- approximation of the true maximum weight matching.
We present several numerical results of experiments investigating the runtime of the algorithm and quality of the obtained results. | |

dc.description.sponsorship | Utrecht University | |

dc.language.iso | EN | |

dc.subject | We propose an approximation algorithm to solve the maximum weight matching problem that is well suited for parallelism. We make use of applying positive-gain k-augmentations in iterations that each require linear time. The end result is a 3/4-approximation of the true maximum weight matching for general graphs. | |

dc.title | A 3/4-approximation of the maximum weight matching problem using the GraphBLAS standard | |

dc.type.content | Master Thesis | |

dc.rights.accessrights | Open Access | |

dc.subject.keywords | GraphBLAS; Maximum weight matching; Graph algorithm; Parallel computing; Approximation algorithm; k-augmentations; linear-time | |

dc.subject.courseuu | Mathematical Sciences | |

dc.thesis.id | 17361 | |