# Accession Number:

## ADA156525

# Title:

## Two Algorithms for Weighted Matroid Intersection.

# Descriptive Note:

## Management science research rept.,

# Corporate Author:

## CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

# Personal Author(s):

# Report Date:

## 1985-03-01

# Pagination or Media Count:

## 26.0

# Abstract:

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.

# Descriptors:

# Subject Categories:

- Statistics and Probability