Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation (Q1950387)

The paper deals with the problem of finding the maximum degree of minors in a mixed polynomial matrix. The authors propose a combinatorial relaxation algorithm for the above problem, which avoids arithmetic operations on rational functions and appears more effective than the previous algorithm of \textit{K. Murota} [SIAM J. Matrix Anal. Appl. 20, No. 1, 196--227 (1998; Zbl 0956.05068)]. The developed algorithm reduces the solution of the considered problem to the solution of a weighted bipartite matching problem and an independent matching problem. The authors apply their algorithm to compute the Kronecker canonical form of a mixed matrix pencil and to the linear valuated independent assignment problem.