Contention Resolution for the ℓ-fold union of a matroid via the correlation gap

The correlation gap of a real-valued set function f : 2^N → R+ [ADSY10] measures the worst-case ratio between two continuous extensions of f over all points in the unit cube; informally the gap measures the worst-case benefit of correlations between the variables. This notion plays an important role in several areas including algorithms for constrained submodular function maximization via contention resolution schemes, mechanism design, and stochastic optimization. The correlation gap of any monotone submodular set function is known to be at least (1 − 1/e), and this bound is tight even for the rank function of a uniform matroid of rank 1. Via a connection established in [CVZ14], this yields an optimal contention resolution scheme for rounding in a matroid polytope. In this paper, we study the correlation gap of the rank function of the ℓ-fold union of a matroid M, denoted by M^ℓ, defined as the (matroid) union of ℓ-copies of M. We prove that the correlation gap of M^ℓ, for any matroid M, is at most 1 − ^{ℓℓe−ℓ} ; this bound behaves as 1 − ^√₂¹_πℓ as ℓ grows. This generalizes the results ℓ! in [Yan11, BFGG22, KS23]. They established this gap for the uniform matroid of rank ℓ which can be viewed as the ℓ-fold union of a uniform matroid of rank 1; moreover this bound is tight even for this special case. The correlation gap yields a corresponding contention resolution scheme for M^ℓ which was the initial motivation for this work.