Towards an Optimal Contention Resolution Scheme for Matchings

11/07/2022
by   Pranav Nuti, et al.
0

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 ⊆ R(x) such that [e ∈ M | e ∈ R(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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset