Greedy Matching Algorithms in Semi-Streaming Environments for Large Bipartite Graphs

Abstract

The maximum weight bipartite matching and the related assignment problem become computationally challenging for large-scale graphs due to the high memory and time demands of optimal algorithms. This thesis investigates the viability of greedy matching algorithms within a semi-streaming environment as a practical approach for such scenarios. Several variations of greedy algorithms, including the ℓ-Local Greedy and the ℓ-Local Double Greedy, were implemented and adapted for the semi-streaming model. Their performance, in terms of solution quality, execution time, and memory requirements, were evaluated against a naive random matching algorithm and the optimal solution. Experiments were mainly conducted using generated bipartite graphs of varying sizes, with a focus on how dividing the data into chunks or shards for semi-streaming impacts performance. The results indicate that greedy algorithms, particularly when adapted for semi-streaming, offer nearoptimal solutions with significantly reduced resource consumption. This means the greedy algorithms are viable for large bipartite graphs where optimal algorithms are infeasible. In conclusion, the ℓ-Local Double Greedy algorithm and especially the ℓ-Local Greedy algorithm are robust, scalable, and give near-optimal solutions for maximum weight bipartite matching in a semi-streaming environment, making them highly valuable tools for large-scale data processing and analysis.