Valuated Matroid Intersection II: Algorithms
Kazuo Murota · SIAM Journal on Discrete Mathematics · 1996
Based on the optimality criteria established in part I [SIAM J. Discrete Math., 9 (1996), pp. 545–561] we show a primal-type cycle-canceling algorithm and a primal–dual-type augmenting algorithm for the valuated independent assignment problem: 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 \{ w(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. The proposed algorithms generalize the previous algorithms for the independent assignment problem as well as for the weighted matroid intersection problem, including those due to Lawler [Math. Prog., 9 (1975), pp. 31–56], Ini and Tomizawa [J. Oper. Res. Soc. Japan, 19 (1976), pp. 32–57], Fujishige [J. Oper. Res. Soc. Japan, 20 (1977), pp. 1–15], Frank [J. Algorithms, 2 (1981), pp. 328–336], and Zimmermann [Discrete Appl. Math., 36 (1992), pp. 179–189].