# New algorithms for linear k -matroid intersection and matroid k -parity problems

- Authors
- Journal
- Mathematical Programming 0025-5610
- Publisher
- Springer-Verlag
- Publication Date
- Disciplines

## Abstract

We present algorithms for the k -Matroid Intersection Problem and for the Matroid k -Parity Problem when the matroids are represented over the field of rational numbers and k > 2. The computational complexity of the algorithms is linear in the cardinality and singly exponential in the rank of the matroids. As an application, we describe new polynomially solvable cases of the k -Dimensional Assignment Problem and of the k -Dimensional Matching Problem. The algorithms use some new identities in multilinear algebra including the generalized Binetâ€”Cauchy formula and its analogue for the Pfaffian. These techniques extend known methods developed earlier for k = 2.

## There are no comments yet on this publication. Be the first to share your thoughts.