A parallel shortest augmenting path algorithm for the assignment problem

DOI10.1145/115234.115349zbMath0799.68111OpenAlexW2013280707MaRDI QIDQ4302861

Paolo Toth, Egon Balas, Joseph F. Pekny, Donald L. Miller

Publication date: 21 August 1994

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/115234.115349

zbMATH Keywords

linear programming parallel algorithms assignment problem parallel processors combinatorial algorithms shortest augmenting path algorithm sparse and very large systems computation on matrices

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Distributed algorithms (68W15)

Related Items

Minimizing variation of production rates in just-in-time systems: A survey, A distributed exact algorithm for the multiple resource constrained sequencing problem, Index Matrices as a Cost Optimization Tool of Resource Provisioning in Uncertain Cloud Computing Environment, Towards auction algorithms for large dense assignment problems, A comment on ``A simple sequencing algorithm for mixed-model assembly lines in just-in-time production systems, Algorithms and codes for dense assignment problems: The state of the art, A Graphics Processing Unit Algorithm to Solve the Quadratic Assignment Problem Using Level-2 Reformulation-Linearization Technique, Solution of large dense transportation problems using a parallel primal algorithm, A note on exploiting the Hamiltonian cycle problem substructure of the asymmetric traveling salesman problem, Efficient index reduction algorithm for large scale systems of differential algebraic equations, A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems, Bicriteria sequencing methods for the mixed-model assembly line in just-in-time production systems, Analysis and solution to the single-level batch production smoothing problem, A comparison of two algorithms for the assignment problem, A data parallel augmenting path algorithm for the dense linear many-to-one assignment problem, Scheduling unit processing time jobs on a single machine with multiple criteria, Lower bounds for nonlinear assignment problems using many body interactions, Parallel primal-dual methods for the minimum cost flow problem