BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-89-1259
       ENTRY:: January 05, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Interior-point methods in parallel computation
        TYPE:: Technical Report
      AUTHOR:: Goldberg, Andrew V.
      AUTHOR:: Plotkin, Serge A.
      AUTHOR:: Shmoys, David B.
      AUTHOR:: Tardos, Eva
        DATE:: May 1989
       PAGES:: 17
    ABSTRACT:: ln this paper we use interior-point methods for linear
               programing, developed in the context of sequential
               computation, to obtain a parallel algorithm for the bipartite
               matching problem. Our algorithm runs in $O^n$(SQRT m) time.
               Our results extend to the weighted bipartite matching problem
               and to the zero-one minimum-cost flow problem, yielding
               $O^n$((SQRT m) log C) algorithms. This improves previous
               bounds on these problems and illustrates the importance of
               interior-point methods in the context of parallel algorithm
               design.
       NOTES:: [Adminitrivia V1/RAM/19950105]
         END:: STAN//CS-TR-89-1259