EFFICIENT THEORETIC AND PRACTICAL ALGORITHMS FOR LINEAR MATROID INTERSECTION PROBLEMS

Efficient algorithms for the matroid intersection problem, both cardin ality and weighted versions, are presented. The algorithm for weighted intersection works by scaling the weights. The cardinality algorithm is a special case, but takes advantage of greater structure. Efficienc y of the algorithms is illustrated by several implementations on linea r matroids. Consider a linear matroid with m elements and rank n. Assu me all element weights are integers of magnitude at most N. Our fastes t algorithms use time O(mn(1.77)log(nN)) and O(mn(1.62)) for weighted and unweighted intersection, respectively; this improves the previous best bounds, O(mn(2.4)) and O(mn(2) log n), respectively. Correspondin g improvements are given for several applications of matroid intersect ion to numerical computation and dynamic systems. (C) 1996 Academic Pr ess, Inc.