Faster Algorithms for Semi-Matching Problems

Author Jittat Fakcharoenphol, Bundit Lekhanukit, Danupon Nanongkai

Download: See ArXiv

Conference: ICALP 2010


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 O(nm\log n)-time algorithm, where n is the number of vertices and m is the number of edges, by exploiting geometric structure of the problem. This improves the classical O(n^3) 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 O(\sqrt{n}m\log n), improving two previous O(nm)-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 O(\sqrt{n}m\log n), improving the previous O(nm)-time algorithm by Harada, Ono, Sadakane and Yamashita [ISAAC 2008].


1 Comment »

  1. Nam~ said

    Hi, I found this site accidentally. Anyway it seems helpful for my homework in integer programming class and I like your webpage.
    PhD student in Clemson

RSS feed for comments on this post · TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: