2021/04/30 by Iwamasa, Yuni
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2104.14841
In this paper, we consider the problem of computing the entire sequence of the maximum degree of minors of a block-structured symbolic matrix (a generic partitioned polynomial matrix) A = (Aαβ xαβ t^dαβ), where Aαβ is a 2 × 2 matrix over a field F, xαβ is an indeterminate, and dαβ is an integer for α= 1,2,…, μ and β= 1,2,…,ν, and t is an additional indeterminate. This problem can be viewed as an algebraic generalization of the maximum weight bipartite matching problem. The main result of this paper is a combinatorial O(μνmin\μ, ν\2)-time algorithm for computing the entire sequence of the maximum degree of minors of a (2 × 2)-type generic partitioned polynomial matrix of size 2μ× 2ν. We also present a minimax theorem, which can be used as a good characterization (NP ∩ co-NP characterization) for the computation of the maximum degree of minors of order k. Our results generalize the classical primal-dual algorithm (the Hungarian method) and minimax formula (Egerváry's theorem) for the maximum weight bipartite matching problem.