Towards an Optimal Contention Resolution Scheme for Matchings

Pranav Nuti and Jan Vondrák

Submitted on 7 November 2022


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 xe, we want to select a matching MR(x) such that Pr[eMeR(x)]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 (in the limit as x goes to 0) optimal 0.544-balanced contention resolution scheme for general matchings, and (ii) a 0.509-balanced contention resolution scheme for bipartite matchings. 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. We also present an application of our scheme to a combinatorial allocation problem, and discuss some open questions related to van der Waerden's conjecture for the permanent of doubly stochastic matrices.


Comment: 22 pages

Subjects: Computer Science - Data Structures and Algorithms; Computer Science - Discrete Mathematics; Mathematics - Probability