Valuated Matroid Intersection I: Optimality Criteria

Abstract

The independent assignment problem (or the weighted matroid intersection problem) is extended using Dress and Wenzel's matroid valuations, which are attached to the vertex set of the underlying bipartite graph as an additional weighting. Specifically, the problem considered is as follows: given a bipartite graph $G = (V^ + ,V^ - ;A)$ with arc weight $w:A \to \mathbf{R}$ and matroid valuations $\omega ^ + $ and $\omega^ - $ on $V^ + $ and $V^ - $ respectively, find a matching $M( \subseteq A)$ that maximizes $\sum \{ \omega (a) \mid a \in M\} + \omega^ + (\partial ^ + M) + \omega^ - (\partial ^ - M)$, where $\partial ^ + M$ and $\partial ^ - M$ denote the sets of vertices in $V^ + $ and $V^ - $ incident to M. As natural extensions of the previous results for the independent assignment problem, two optimality criteria are established: one in terms of potentials and the other in terms of negative cycles in an auxiliary graph.