A Matroid Algorithm and Its Application to the Efficient Solution of Two Optimization Problems on Graphs.
Management sciences research rept.,
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
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 OlVlcubed. 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.
- Theoretical Mathematics