Affordable Access

Publisher Website

Matroid optimization with generalized constraints

Authors
Journal
Discrete Applied Mathematics
0166-218X
Publisher
Elsevier
Publication Date
Volume
63
Issue
2
Identifiers
DOI: 10.1016/0166-218x(94)00031-8
Keywords
  • Matroid Intersection
  • Constrained Optimization
  • Partition Matroid
  • Convexity
  • Recognition Problems
Disciplines
  • Computer Science

Abstract

Abstract 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 base in the matroid subject to linear inequality constraints on colors is explored. The color constraints are shown to form a strict hierarchy based on increasingly stronger notions of convexity. The concept of a lattice of color vectors and associated minimum cost bases is introduced. 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 constrained problem must occur at constraint boundaries, allowing earlier algorithms for a simpler version of the problem to be extended. Finally, it is shown that a given set of constraints can be located within the hierarchy in polynomial time.

There are no comments yet on this publication. Be the first to share your thoughts.