Faster Algorithms for Semi-Matching Problems
Jittat Fakcharoenphol, Bundit Laekhanukit, Danupon Nanongkai · ACM Transactions on Algorithms · 2014
We consider the problem of finding semi-matching in bipartite graphs, which is also extensively studied under various names in the scheduling literature. We give faster algorithms for both weighted and unweighted cases. For the weighted case, we give an O ( nm log n )-time algorithm, where n is the number of vertices and m is the number of edges, by exploiting the geometric structure of the problem. This improves the classical O ( n 3 )-time algorithms by Horn [1973] and Bruno et al. [1974b]. For the unweighted case, the bound can be improved even further. We give a simple divide-and-conquer algorithm that runs in O (√ nm log n ) time, improving two previous O ( nm )-time algorithms by Abraham [2003] and Harvey et al. [2003, 2006]. We also extend this algorithm to solve the Balanced Edge Cover problem in O (√ nm log n ) time, improving the previous O ( nm )-time algorithm by Harada et al. [2008].