JavaScript is disabled for your browser. Some features of this site may not work without it.

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

Barvinok, Alexander I.

Barvinok, Alexander I.

1995-07

Citation:Barvinok, Alexander I.; (1995). "New algorithms for linear k -matroid intersection and matroid k -parity problems." Mathematical Programming 69 (1-3): 449-470. <http://hdl.handle.net/2027.42/47928>

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.