Details

Autor(en) / Beteiligte

• Iwamasa, Yuni

Titel

A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with 2×2 submatrices

Ist Teil von

• Mathematical programming, 2024, Vol.204 (1-2), p.27-79

Ort / Verlag

Berlin/Heidelberg: Springer Berlin Heidelberg

Erscheinungsjahr

2024

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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 -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.