A combinatorial algorithm for computing the entire sequence of themaximum degree of minors of a generic partitioned polynomialmatrix with 2 x 2 submatrices

• 成果类型: Article
• 署名作者: Iwamasa, Yuni
• 署名单位: Kyoto University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-01949-1
• 发表日期: 2024
• 页码: 27-79
• 关键词: discrete convex-optimization; maximum degree; relaxation algorithm; matrix; rank

摘要

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 = ( Aa ss xa ss t(da ss)), where A(a ss) is a 2x2 matrix over a field F, x(a ss) is an indeterminate, and d(a ss) is an integer for a = 1, 2,..., mu and ss = 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(mu nu min{mu,nu}(2))-time algorithm for computing the entire sequence of themaximum degree ofminors of a (2x2)-type generic partitioned polynomial matrix of size 2 mu x2.. We also present a minimax theorem, which can be used as a good characterization (NP n co-NP characterization) for the computation of the maximum degree of minors of order k. Our results generalize the classical primaldual algorithm (the Hungarian method) and minimax formula (Egervary's theorem) for the maximum weight bipartite matching problem.