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.