| dc.rights.license | CC-BY-NC-ND | |
| dc.contributor.advisor | Bisseling, Rob | |
| dc.contributor.author | Kemper, Jetske | |
| dc.date.accessioned | 2022-04-01T00:00:43Z | |
| dc.date.available | 2022-04-01T00:00:43Z | |
| dc.date.issued | 2022 | |
| dc.identifier.uri | https://studenttheses.uu.nl/handle/20.500.12932/41451 | |
| dc.description.abstract | The maximum weight matching problem for general graphs is a well-studied problem with a
variety of approximation algorithms already existing. Yet, many of them are hard to parallelize.
Therefore, we propose a 3/4-approximation algorithm completely built on matrix operations in
GraphBLAS. The idea is that these operations are more straightforward to parallelize. The algorithm is based on finding and flipping positive-gain augmentations. | |
| dc.description.sponsorship | Utrecht University | |
| dc.language.iso | EN | |
| dc.subject | The maximum weight matching problem for general graphs is a well-studied problem with a
variety of approximation algorithms already existing. Yet, many of them are hard to parallelize.
Therefore, we propose a 3/4-approximation algorithm completely built on matrix operations in
GraphBLAS. The idea is that these operations are more straightforward to parallelize. The algorithm is based on finding and flipping positive-gain augmentations. | |
| dc.title | Approximating the maximum weight matching problem using the GraphBLAS standard | |
| dc.type.content | Master Thesis | |
| dc.rights.accessrights | Open Access | |
| dc.subject.keywords | Maximum weight matching problem; Approximation algorithm; GraphBLAS; Positive-gain augmentations | |
| dc.subject.courseuu | Mathematical Sciences | |
| dc.thesis.id | 3163 | |
