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*( square root m) time. The results extend to the weighted bipartite matching problem and to the zero-one minimum-cost flow problem, yielding O*( square root m log C) algorithms. This improves previous bounds on these problems and illustrates the importance of interior-point methods in parallel algorithm design. >

Authors

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

Keywords

• Concurrent computing
• Parallel algorithms
• Contracts
• Linear programming
• Bipartite graph
• Operations research
• Algorithm design and analysis
• Uninterruptible power systems
• Sun
• Costs
• Parallelization
• Interior Point
• Interior Point Method
• Objective Function
• Value Function
• Feasible Solution
• Linear Problem
• Maximum Weight
• Affine Transformation
• Maximum Flow
• Quadratic Programming
• Current Solution
• Algorithm For Problem
• Linear Algorithm
• Sequential Algorithm
• Similar Algorithms
• Dual Problem
• Slack Variables