dc.contributor.author | Zaicevs, Nikita | |
dc.date.accessioned | 2024-07-15T23:58:36Z | |
dc.date.available | 2024-07-15T23:58:36Z | |
dc.date.issued | 2024-06-03 | |
dc.date.submitted | 2024-06-03T10:07:01Z | |
dc.identifier | INF399 0 O ORD 2024 VÅR | |
dc.identifier.uri | https://hdl.handle.net/11250/3141363 | |
dc.description.abstract | In this work we train a graph neural network model to solve the Maximum Weighted
Matching problem on graphs using supervised learning. Unfortunately, the final results
were below the set expectations. The model seemed to be slightly worse than a standard
greedy algorithm, mainly because the greedy algorithm on average performed very well
compared to the optimal solution. However, the neural network did show potential at
solving the problem for more narrow graph datasets and graphs that were particularly
difficult for the greedy algorithm. The results do not imply that graph neural networks
in general cannot beat greedy algorithms, but rather suggest that different approaches or
further improvement are needed. | |
dc.language.iso | eng | |
dc.publisher | The University of Bergen | |
dc.rights | Copyright the Author. All rights reserved | |
dc.subject | Maximum Weighted Matching, Graph Neural Network, Machine learning | |
dc.title | Solving Maximum Weighted Matching problem using Graph Neural Networks | |
dc.title.alternative | Solving Maximum Weighted Matching problem using Graph Neural Networks | |
dc.type | Master thesis | |
dc.date.updated | 2024-06-03T10:07:01Z | |
dc.rights.holder | Copyright the Author. All rights reserved | |
dc.description.degree | Masteroppgave i informatikk | |
dc.description.localcode | INF399 | |
dc.description.localcode | MAMN-PROG | |
dc.description.localcode | MAMN-INF | |
dc.subject.nus | 754199 | |
fs.subjectcode | INF399 | |
fs.unitcode | 12-12-0 | |