An algorithm for weighted fractional matroid matching

Abstract

Let M be a matroid on ground set E with rank function r. A subset l⊆E is called a line when r(l)∈{1,2}. Given a finite set L of lines in M, a vector x∈R+L is called a fractional matching when ∑l∈Lxla(F)l⩽r(F) for every flat F of M. Here a(F)l is equal to 0 when l∩F=∅, equal to 2 when l⊆F and equal to 1 otherwise. We refer to ∑l∈Lxl as the size of x.It was shown by Chang et al. [S. Chang, D. Llewellyn, J. Vande Vate, Matching 2-lattice polyhedra: finding a maximum vector, Discrete Math. 237 (2001) 29–61], that a maximum size fractional matching can be found in polynomial time. In this paper we give a polynomial time algorithm to find, for given weight function w:L→Q, a maximum weight fractional matching. A simple reference to the equivalence of separation and optimization does not lead to such an algorithm, since no direct method for polynomial time separation is known for this polytope.