2025/02/28 by Kwok, Shawxing
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2502.20889
Given a weighted bipartite graph G = (L, R, E, w), the maximum weight matching (MWM) problem seeks to find a matching M ⊆ E that maximizes the total weight ∑e ∈ M w(e). This paper presents a novel algorithm with a time complexity of O(min(X3 + E, XE + X2log X)), where X = min(|L|, |R|). Unlike many existing algorithms, our approach supports real-valued weights without additional constraints. Under this condition, our result improves upon the previous best-known bound of O(VE + V2log V), or more strictly O(XE + XVlog V), where V = L ∪ R. The suggested implementation code is simplified and publicly available at https://github.com/ShawxingKwok/Kwok-algorithm, with the average-case time complexity of O(E1.4 + LR) estimated from experimental results on random graphs.