Contributions to the hungarian method
The Hungarian method is an algorithm due to Kuhn for solving in a finite number of steps the linear assignment problem with integer or rational coefficients. It is based on a theorem of König-Egervàry, stating that if the maximal number of independent zeroes of a matrix is m, then m lines (rows or columns) may be chosen, which cover all zeroes (two elements are independent if they do not lie on a line). In this paper a counterexample is exhibited of an assignment problem with real entries, for which the Hungarian method never stops. Next, two possible extensions of the König-Egervàry theorem to three- dimensional matrices (first replacing lines by planes, then coming back to lines) are shown to be false. The author concludes that the Hungarian method is not extendable to higher dimensional assignment problems.
- Improving the Hungarian assignment algorithm
- Revisiting the 0,1 assignment problem
- A tale of three eras: the discovery and rediscovery of the Hungarian method
- Modified Hungarian method for unbalanced assignment problem with multiple jobs
- On the Wald's sequential probability ratio test for Lévy processes
- A note on Hungarian algorithm for assignment problems
- On the problem of transversal selection
- Un algoritmo misto per il problema dell'assegnazione pluridimensionale
- Extension of Egervàry theorem on optimal solution of assignment problem: logical approach
- The Hungarian method for the assignment problem
- Depth search: remarks on the history of algorithms
- scientific article; zbMATH DE number 3991510 (Why is no real title available?)
- scientific article; zbMATH DE number 4091179 (Why is no real title available?)
- scientific article; zbMATH DE number 1179832 (Why is no real title available?)
- On Kuhn's Hungarian Method?A tribute from Hungary
- A comprehensive simplex-like algorithm for network optimization and perturbation analysis
- Purcell's method, Egerváry and related results
- Jenő Egerváry: from the origins of the Hungarian algorithm to satellite communication
- Admissible transformations and assignment problems
This page was built for publication: Contributions to the hungarian method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3323707)