Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with 2×2 submatrices
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.