Two Algorithms for Weighted Matroid Intersection.

Abstract

Consider a finite set E, a weight function w:E 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 w(e): e in 1. This improves the complexity of earlier algorithms by a factor r, when c < or = O(n), and by a factor n when max(c, log n) < or = O(r). 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1985
Accession Number
ADA156525

Entities

People

  • C. Brezovec
  • F. Glover
  • G. Cornuejols

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • C4I
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Colorado
  • Computations
  • Computer Science
  • Construction
  • Equations
  • Guarantees
  • Inequalities
  • Iterations
  • Mathematics
  • Military Research
  • New York
  • Optimization
  • Recognition
  • Schools
  • Sensitivity
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research