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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/95/1556/CS-TR-95-1556.pdf