MATROID OPTIMIZATION WITH GENERALIZED CONSTRAINTS

Matroids of rank n are studied in which each element has a real-valued cost and one of d > 1 colors. The problem of finding a minimum cost b ase in the matroid subject to linear inequality constraints on colors is explored. The color constraints are shown to form a strict hierarch y based on increasingly stronger notions of convexity. The concept of a lattice of color vectors and associated minimum cost bases is introd uced. The relationship of the cost of a base to those of its neighbors in the lattice is examined. It is shown that the solution to the cons trained problem must occur at constraint boundaries, allowing earlier algorithms for a simpler version of the problem to be extended. Finall y, it is shown that a given set of constraints can be located within t he hierarchy in polynomial time.