Contributions to the hungarian method

From MaRDI portal
Publication:3323707





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.











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)