Improving the Hungarian assignment algorithm
From MaRDI portal
We describe three easily implementable improvements for the Hungarian linear assignment algorithm. Computation times vary from about two to more than three times lower than previously, where the effectiveness increases with problem size. Furthermore, the algorithm is now less sensitive to the range of the cost coefficients. We also show that the Hungarian algorithm is essentially equivalent to assignment algorithms based on shortest augmenting paths.
Recommendations
Cites work
- A new algorithm for the assignment problem
- Algorithm for the solution of the assignment problem for sparse matrices
- An algorithm for the assignment problem
- Efficient dual simplex algorithms for the assignment problem
- scientific article; zbMATH DE number 3558962 (Why is no real title available?)
- scientific article; zbMATH DE number 3231692 (Why is no real title available?)
- Implementation and Testing of a Primal-Dual Algorithm for the Assignment Problem
- Relaxation Methods for Minimum Cost Ordinary and Generalized Network Flow Problems
- Signature Methods for the Assignment Problem
Cited in
(37)- An addendum on the incremental assignment problem
- Authors' response to ``An addendum on the incremental assignment problem by Volgenant
- A shortest augmenting path algorithm for dense and sparse linear assignment problems
- Travelling salesman problem tools for microcomputers
- Personnel placement in a fuzzy environment
- A new algorithm for the assignment problem: An alternative to the Hungarian method
- Lower tolerance-based branch and bound algorithms for the ATSP
- Speeding up the Hungarian algorithm
- Algorithms and codes for dense assignment problems: The state of the art
- Efficient computation of tolerances in the sensitivity analysis of combinatorial bottleneck problems
- The stable marriage problem: an interdisciplinary review from the physicist's perspective
- The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems
- Tolerance-based branch and bound algorithms for the ATSP
- An algorithm for ranking assignments using reoptimization
- Iterative patching and the asymmetric traveling salesman problem
- Sensitivity analysis for bottleneck assignment problems
- The computational efficiency of Ji-Lee-Li algorithm for the assignment problem
- Contributions to the hungarian method
- Un algoritmo misto per il problema dell'assegnazione pluridimensionale
- Study on the Hungarian algorithm for the maximum likelihood data association problem
- Parallel Auction Algorithm for Bus Rescheduling
- Analysis and automatization of the Edmonds algorithm for the assignment problem
- Incremental Processing Applied to Munkres’ Algorithm and Its Application in Steinberg’s Placement Procedure
- Remarks on implementation of O ( n 1/2 τ) assignment algorithms
- scientific article; zbMATH DE number 4091179 (Why is no real title available?)
- scientific article; zbMATH DE number 4127004 (Why is no real title available?)
- scientific article; zbMATH DE number 1179832 (Why is no real title available?)
- Multistart Branch and Bound for Large Asymmetric Distance-Constrained Vehicle Routing Problem
- A comprehensive simplex-like algorithm for network optimization and perturbation analysis
- Index matrices as a cost optimization tool of resource provisioning in uncertain cloud computing environment
- Node matching computation between two large graphs in linear computational cost
- ThIEF: finding genome-wide trajectories of epigenetics marks
- Kalman filtering with censored measurements
- Multi-agent target defense differential game: a hierarchical recognition-allocation-execution learning approach
- Efficient online sensitivity analysis for the injective bottleneck path problem
- A decision support system for the single-depot vehicle rescheduling problem
- A note of reduced dimension optimization algorithm of assignment problem
This page was built for publication: Improving the Hungarian assignment algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1085073)
