Report Number: CS-TR-95-1556
Institution: Stanford University, Department of Computer Science
Title: Solving Unweighted and Weighted Bipartite Matching Problems
in Theory and Practice
Author: Kennedy, J. Robert, Jr.
Date: August 1995
Abstract: The push-relabel method has been shown to be efficient for
solving maximum flow and minimum cost flow problems in
practice, and periodic global updates of dual variables have
played an important role in the best implementations.
Nevertheless, global updates had not been known to yield any
theoretical improvement in running time. In this work, we
study techniques for implementing push-relabel algorithms to
solve bipartite matching and assignment problems. We show
that global updates yield a theoretical improvement in the
bipartite matching and assignment contexts, and we develop a
suite of efficient cost-scaling push-relabel implementations
to solve assignment problems.
For bipartite matching, we show that a push-relabel algorithm
using global updates matches the best time bound known
(roughly the number of edges times the square root of the
number of nodes --- better for dense graphs) and performs
worse by a factor of the square root of the number of nodes
without the updates. We present a similar result for the
assignment problem, for which an algorithm that assumes
integer costs has running time asymptotically dominated by
the number of edges times the number of nodes times a scaling
factor logarithmic in the number of nodes and the largest
magnitude of an edge cost in the problem. The bound we obtain
matches the best cost-scaling bound known.
We develop cost-scaling push-relabel implementations that
take advantage of the assignment problem's special structure,
and compare our codes against the best codes from the
literature. The results show that the push-relabel method is
very promising for practical use.