Accession Number : ADA322743

Title :   Interior-Point Methods in Parallel Computation,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Goldberg, Andrew V. ; Plotkin, Serge A. ; Shmoys, David B. ; Tardos, Eva

PDF Url : ADA322743

Report Date : MAY 1989

Pagination or Media Count : 18

Abstract : In this paper we use interior-point methods for linear programming, developed in the context of sequential computation, to obtain a parallel algorithm for the bipartite matching problem. Our algorithm runs in O(square root of m) time. Our results extend to the weighted bipartite matching problem and to the zero-one minimum-cost flow problem, yielding O((square root of m) logC) algorithms. This improves previous bounds on these problems and illustrate the importance of interior-point methods in the context of parallel algorithm design.

Descriptors :   *LINEAR PROGRAMMING, *PARALLEL PROCESSING, ALGORITHMS, MATRICES(MATHEMATICS), WEIGHTING FUNCTIONS, MAPPING(TRANSFORMATIONS).

Subject Categories : Operations Research
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE