Matroid intersection algorithms

LetM ₁ = (E, 9₁),M ₂ = (E, 9₂) be two matroids over the same set of elementsE, and with families of independent sets 9₁, 9₂. A setI 9₁ 9₂ is said to be anintersection of the matroidsM ₁,M ₂. An important problem of combinatorial optimization is that of finding an optimal intersection ofM ₁,M ₂. In this paper three matroid intersection algorithms are presented. One algorithm computes an intersection containing a maximum number of elements. The other two algorithms compute intersections which are of maximum total weight, for a given weighting of the elements inE. One of these algorithms is primal-dual, being based on duality considerations of linear programming, and the other is primal. All three algorithms are based on the computation of an augmenting sequence of elements, a generalization of the notion of an augmenting path from network flow theory and matching theory. The running time of each algorithm is polynomial inm, the number of elements inE, and in the running times of subroutines for independence testing inM ₁,M ₂. The algorithms provide constructive proofs of various important theorems of matroid theory, such as the Matroid Intersection Duality Theorem and Edmonds' Matroid Polyhedral Intersection Theorem.Research sponsored by the Air Force Office of Scientific Research Grant 71-2076.