GLOBAL PRICE UPDATES HELP

Periodic global updates of dual variables have been shown to yield a s ubstantial speed advantage in implementations of push-relabel algorith ms 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 (root nm log(n(2)/m)/log n) time (matching the best bound lo g n known) and performs worse by a factor of root n without the update s. A similar result holds for the assignment problem, for which an alg orithm that assumes integer costs in the range [-C,...,C] and that run s in time O(root nm log(nC)) (matching the best cost-scaling bound kno wn) is presented.