Global Price Updates Help

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 uses global updates runs in O(√ n mlog(n²/m)/log n) time (matching the best bound known) and performs worse by a factor of √ n without the updates. A similar result holds for the assignment problem, for which an algorithm that assumes integer costs in the range [\,-C,…, C\,] and that runs in time O(√ n mlog(nC)) (matching the best cost-scaling bound known) is presented.