Generalising the Kőnig‐Egerváry theorem

Abstract

Purpose

The purpose of this paper is to consider extension of the Kőnig‐Egerváry theorem to apply to matrices of dimensionality greater the two. It is shown that the theorem holds for matrices of any dimensionality, in the standard case where “cover” of selected elements is by lines, and the criterion for independence is also with reference to lines. Attention is also given to the case where cover and (hyper‐independence) are with reference to planes, or submatrices of higher dimensionality, rather than lines, and counter‐examples are given that show the theorem does not then hold universally. A preliminary survey is made of the diverse proofs that have been devised for the basic theorem, and in an Appendix an approach to the multidimensional Transportation Problem is reviewed.

Design/methodology/approach

Interest in generalisation of the theorem arose from the attempt to extend the Hungarian Method for the Assignment Problem to higher dimensionality. The results are also interesting as purely mathematical theory.

Findings

The theorem has been shown to extend to the multidimensional case when cover and independence are defined with reference to lines, but not universally otherwise.

Practical implications

Extension of the theorem to higher dimensionality has not produced a rigorous corresponding extension of the Hungarian Method, but may stimulate further studies. An approximate extension of the method (approximate insofar as it gives no guarantee of convergence on an optimum) will be described in a later publication. The study of the multidimensional Transportation Problem, reviewed in the Appendix, confirms the general difficulty of extending a class of methods from elegant solutions in the two‐dimensional case to versions for higher dimensionality.

Originality/value

The paper's results are believed to be original. Their main value is likely to be in stimulating interest that may lead to further developments as suggested.

Citation

Andrew, A. (2013), "Generalising the Kőnig‐Egerváry theorem", Kybernetes, Vol. 42 No. 4, pp. 628-640. https://doi.org/10.1108/K-10-2012-0084