Valuated Matroid Intersection I: Optimality Criteria
Kazuo Murota · SIAM Journal on Discrete Mathematics · 1996
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.