**Author** Jittat Fakcharoenphol, Bundit Lekhanukit, Danupon Nanongkai

**Download:** See ArXiv

**Conference: **ICALP 2010

**Abstract:**

We consider the problem of finding *semi-matching* in bipartite graphs, a problem also extensively studied under various names in the scheduling literature. We give faster algorithms for both weighted and unweighted case.

For the weighted case, we give an -time algorithm, where is the number of vertices and is the number of edges, by exploiting geometric structure of the problem. This improves the classical algorithms by Horn [Operations Research 1973] and Brono, Coffman and Sethi [Communications of the ACM 1974].

For the unweighted case, the bound could be improved even further. We give a simple divide-and-conquer algorithm which runs in time , improving two previous -time algorithms by Abraham [MSc thesis, University of Glasgow 2003] and Harvey, Ladner, Lovasz and Tamir [WADS 2003 and Journal of Algorithms 2006]. We also extend this algorithm to solve the *Balance Edge Cover* problem in time , improving the previous -time algorithm by Harada, Ono, Sadakane and Yamashita [ISAAC 2008].