Maximum weighted matching on a GPU

Abstract

In this thesis we give the first parallel GPU-implementation of the ROMA algorithm suited for complete graphs. ROMA is an approximation algorithm solving the maximum weighted matching problem. Our algorithm achieves an average speedup of 207 on our input graphs when comparing it to the sequential algorithm, while still giving equally good matchings.