Solving a combinatorial problem with network flows (Q1767398)

The authors consider the following problem: given a matrix \(M\) with \(n\) rows and \(k\) columns, \(n\geq k\), choose an element from each column, such that no pair of elements is in the same row, and that the sum of all elements is minimal. When \(n=k\) the problem coincides with the assignment problem solved by the Hungarian algorithm, which is further equivalent to the problem of finding a minimal weighted perfect matching in a bipartite graph. An algorithm finding all solutions to the later problem in case \(n=k\) has been provided by \textit{K. Fukuda} and \textit{T. Matsui} [Networks 22, 461--468 (1992; Zbl 0762.90080)]. Here the authors generalize the algorithm of Fukuda and Matsui to the case when \(n>k\).