Interior-Point Methods in Parallel Computation,

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1989
Accession Number
ADA322743

Entities

People

  • Andrew V. Goldberg
  • David Shmoys
  • Serge A. Plotkin
  • Éva Tardos

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Availability
  • Classification
  • Coefficients
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Contracts
  • Graph Theory
  • Integrals
  • Iterations
  • Linear Programming
  • Mathematics
  • Parallel Computing
  • Security

Fields of Study

  • Mathematics

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Logistics and Supply Chain Management.