Auction Algorithms for Matchings in Bipartite Graphs
Published in UOB COMSM0052 Individual Computer science project, 2022
This project is final year project for Master course.
Abstract
Matching in bipartite graph is the problem of finding the largest set of edges selected in a way such that no two edges share the same node. While this problem is well-known and is a central problem in graph theory algorithms.
However, the most advanced algorithm for this matching problem cannot handle today’s explosive data growth. Recently, a theoretically optimised streaming algorithm, called the auction algorithm, can cope with large amounts of data. Our project aims to research this auction matching algorithm and give a more in-depth analysis and engineering optimisation. We give worst-case theoretical analyses and validate these analyses through our experiments and visualisations. Based on the original auction algorithm and analyses, we propose several points that can be optimised from an engineering perspective.
Finally, through experiments on 15 different datasets, we compare the following three algorithms in terms of the number of iterations and run-time in practical.
- The current state-of-the-art Edmond’s matching algorithm
- The new auction matching algorithm
- The improved auction matching algorithm