A Matroid Algorithm and Its Application to the Efficient Solution of Two Optimization Problems on Graphs.

Abstract

This document addresses the problem of finding a minimum weight base B of a matroid when, in addition, each element of the matroid is colored with one of m colors and there are upper and lower bound restrictions on the number of elements of B with color i, for i = 1,2, ..., m. This problem is a special case of matroid intersection. The authors present an algorithm that exploits the special structure. When applied to the weighted bipartite matching problem, this algorithm has complexity O(lVlcubed). In both cases, V denotes the node set of the underlying graph, and E denotes its edge set. Also discussed is a new relaxation for the traveling salesman problem.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1987
Accession Number
ADA180342

Entities

People

  • Carl Brezovec
  • Fred Glover
  • Gérard Cornuéjols

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Construction
  • Guarantees
  • Inequalities
  • Iterations
  • Mathematical Programming
  • Mathematics
  • Military Research
  • New York
  • Optimization
  • Recognition
  • Splitting
  • Universities

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research