Valuated Matroid Intersection II: Algorithms

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 → R and matroid valuations ω^ + and ω ^ - on V^ + and V^ -, respectively; find a matching M( ⊆ A) that maximizes ∑ \ w(a) a ∈ M\ + ω^ + (∂ ^ + M) + ω^ - (∂ ^ - M), where ∂ ^ + M and ∂ ^ - 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].