Two Algorithms for Weighted Matroid Intersection.
Management science research rept.,
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
Consider a finite set E, a weight function wE approaches R, and two matroids M1 and M2 defined on E. The weighted matroid intersection problem consists of finding a set of E, independent in both matroids, that maximizes sigma E we e in 1. This improves the complexity of earlier algorithms by a factor r, when c or On, and by a factor n when maxc, log n or Or. A related problem is to find a maximum weight set, independent in both matroids, and of given cardinality k if one exists. Our algorithm also solves this problem. In addition, we present a second algorithm which, given a feasible solution of cardinality k, finds an optimal one of the same cardinality. A sensitivity analysis on the weights is easy to perform using this approach.
- Statistics and Probability