BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-94-1509
       ENTRY:: March 22, 1994
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Global Price Updates Help
        TYPE:: Technical Report
      AUTHOR:: Goldberg, Andrew V.
      AUTHOR:: Kennedy, Robert
       PAGES:: 18
    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.
       NOTES:: [Adminitrivia V1/Prg/19940322]
         END:: STAN//CS-TR-94-1509