Competitive Weighted Matching in Transversal Matroids

Consider a bipartite graph with a set of left‐vertices and a set of right‐vertices. All the edges adjacent to the same left‐vertex have the same weight. We present an algorithm that, given the set of right‐vertices and the number of left‐vertices, processes a uniformly random permutation of the left‐vertices, one left‐vertex at a time. In processing a particular left‐vertex, the algorithm either permanently matches the left‐vertex to a thus‐far unmatched right‐vertex, or decides never to match the left‐vertex. The weight of the matching returned by our algorithm is within a constant factor of that of a maximum weight matching, generalizing the recent results of Babaioff et al.