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.

Subject Categories:

  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE