|
Nicholas J. A. Harvey, Richard E. Ladner, Laszlo Lovasz, Tami Tamir.
Workshop on Algorithms and Data Structures (WADS 2003),
Ottawa, Canada, July 2003.
PDF PS Slides.
Journal of Algorithms,
59(1):53-78,
2006.
PDF PS.
We consider the problem of fairly matching the left-hand vertices of a bipartite graph to the
right-hand vertices. We refer to this problem as the semi-matching problem; it is a relaxation of
the known bipartite matching problem. We present a way to evaluate the quality of a given
semi-matching and show that, under this measure, an optimal semi-matching balances the load on the
right hand vertices with respect to any Lp-norm. In particular, when modeling a job assignment
system, an optimal semi-matching achieves the minimal makespan and the minimal flow time for the
system.
The problem of finding optimal semi-matchings is a special case of certain scheduling problems for
which known solutions exist. However, these known solutions are based on general network
optimization algorithms, and are not the most efficient way to solve the optimal semi-matching
problem. To compute optimal semi-matchings efficiently, we present and analyze two new algorithms.
The first algorithm generalizes the Hungarian method for computing maximum bipartite matchings,
while the second, more efficient algorithm is based on a new notion of cost-reducing paths. Our
experimental results demonstrate that the second algorithm is vastly superior to using known network
optimization algorithms to solve the optimal semi-matching problem. Furthermore, this same algorithm
can also be used to find maximum bipartite matchings and is shown to be roughly as efficient as the
best known algorithms for this goal.
|