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 design.

http://i.stanford.edu/pub/cstr/reports/cs/tr/89/1259/CS-TR-89-1259.pdf