Report Number: CS-TR-89-1259
Institution: Stanford University, Department of Computer Science
Title: Interior-point methods in parallel computation
Author: Goldberg, Andrew V.
Author: Plotkin, Serge A.
Author: Shmoys, David B.
Author: Tardos, Eva
Date: May 1989
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