Affordable Access

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

Authors
Journal
Mathematical Programming
0025-5610
Publisher
Springer-Verlag
Publication Date
Disciplines
  • Computer Science
  • Mathematics

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.