Interior-point methods in parallel computation

Interior-point methods for linear programming, developed in the context of sequential computation, are used to obtain a parallel algorithm for the bipartite matching problem. The algorithm runs in O*(√m) time. The results extend to the weighted bipartite matching problem and to the zero-one minimum-cost flow problem, yielding O*(√m log C) algorithms. This improves previous bounds on these problems and illustrates the importance of interior-point methods in parallel algorithm design