A Shortest Augmenting Path Algorithm for the Semi-Assignment Problem

DOI10.1287/OPRE.40.1.178MaRDI QIDQ3991331zbMATH OpenOpenAlexFDO

Authors Jeffery L. Kennington, Zhiming Wang

Publication date 28 June 1992

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/opre.40.1.178

zbMATH Keywords

semi-assignment problemshortest augmenting path algorithm

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Deterministic network models in operations research (90B10) Discrete location and assignment (90B80) Linear programming (90C05) Boolean programming (90C09) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• scientific article; zbMATH DE number 515939
• A parallel shortest augmenting path algorithm for the assignment problem
• A shortest augmenting path algorithm for dense and sparse linear assignment problems
• Massively parallel augmenting path algorithms for the assignment problem
• scientific article; zbMATH DE number 2163908
• A simple efficient approximation scheme for the restricted shortest path problem
• Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems
• A novel pseudo‐polynomial approach for shortest path problems
• An Incremental Algorithm for a Generalization of the Shortest-Path Problem
• Augment-insert algorithms for the capacitated arc routing problem

Cited in

(21)

• A shortest augmenting path algorithm for dense and sparse linear assignment problems
• An O(n) bound for the diameter of transshipment polytopes
• The singly constrained assignment problem: A Lagrangian relaxation heuristic algorithm
• A note on the assignment problem with seniority and job priority constraints.
• Linear assignment procedures
• A data parallel augmenting path algorithm for the dense linear many-to-one assignment problem
• Solving the k-cardinality assignment problem by transformation
• The singly constrained assignment problem: An AP basis algorithm
• Variational approximation of interface energies and applications
• Linear and semi-assignment problems: A core oriented approach
• scientific article; zbMATH DE number 4130203 (Why is no real title available?)
• Threshold assignment algorithm
• scientific article; zbMATH DE number 515939 (Why is no real title available?)
• A parallel shortest augmenting path algorithm for the assignment problem
• Polynomial-Time Highest-Gain Augmenting Path Algorithms for the Generalized Circulation Problem
• Exact algorithms for distributionally \(\beta \)-robust machine scheduling with uncertain processing times
• FPT algorithms for a special block-structured integer program with applications in scheduling
• Singleton node consistency for quadratic assignment problems in cost function networks
• Assignment problems: a golden anniversary survey
• Bicriterion scheduling with equal processing times on a batch processing machine
• The multi-period incremental service facility location problem

This page was built for publication: A Shortest Augmenting Path Algorithm for the Semi-Assignment Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3991331)