In this paper, we study contention resolution schemes for matchings. Given a fractional matching x and a random set R(x) where each edge e appears independently with probability \(x_e\) , we want to select a matching \(M \subseteq R(x)\) such that \(\Pr [e \in M \mid e \in R(x)] \ge c\) , for c as large as possible. We call such a selection method a c-balanced contention resolution scheme. Our main results are (i) an asymptotically optimal \(\simeq 0.544\) -balanced contention resolution scheme for general matchings when \(\Vert x\Vert _\infty \rightarrow 0\) , and (ii) a 0.509-balanced contention resolution scheme for bipartite matchings (without any restriction on x). To the best of our knowledge, this result establishes for the first time, in any natural relaxation of a combinatorial optimization problem, a separation between (i) offline and random order online contention resolution schemes, and (ii) monotone and non-monotone contention resolution schemes.
