Report Number: CS-TR-94-1509
Institution: Stanford University, Department of Computer Science
Title: Global Price Updates Help
Author: Goldberg, Andrew V.
Author: Kennedy, Robert
Date: March 1994
Abstract: Periodic global updates of dual variables have been shown to yield a substantial speed advantage in implementations of push-relabel algorithms for the maximum flow and minimum cost flow problems. In this paper, we show that in the context of the bipartite matching and assignment problems, global updates yield a theoretical improvement as well. For bipartite matching, a push-relabel algorithm that matches the best bound when global updates are used achieves a bound that is worse by a square root of n factor without the updates. A similar result holds for the assignment problem.