A Multiply Constrained Matroid Optimization Problem

Leclerc, Matthias and Rendl, Franz (1989) A Multiply Constrained Matroid Optimization Problem.
Published in: Discrete mathematics Vol. 73 (1-2). pp. 207-212.

Abstract

We consider the problem of finding a minimum weight basis of a matroid satisfying additional conditions which can be described as follows: each element of the matroid is assigned a color and feasible bases can use at most a prescribed number of elements from each color. This problem is a special case of weighted matroid intersection. We provide an algorithm for this problem which improves general matroid intersection algorithms by exploiting the simple structure of the side constraints.


Actions:
Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr87-040
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Jan 2012 12:28
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/40