Valuated matroid intersection .2. 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 are weight w : A --> R and matroid valuations omega(+) and omega(-) on V+ and V-, respectively, find a matching M(subset of or equal to A) that maximizes Sigma{w(a) \ a is an element of M} + omega(+)(partial derivative(+) M) + omega(-) (partial derivative(-) M), where partial derivative(+) M and partial derivative(-) 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], Iri and Tomizawa [J. Oper. Res. Sec. Japan, 19 (1976), pp. 32-57], Fujishige [J. Oper. Res. Sec. Japan, 20 (1977), pp. 1-15], Frank [J. Algorithms, 2 (1981), pp. 328-336], and Zimmermann [Discrete Appl. Math., 36 (1992), pp. 179-189].