TY - GEN

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

AU - Chekuri, Chandra

AU - Song, Junkai

AU - Zhang, Weizhong

N1 - Publisher Copyright:
Copyright © 2024 by SIAM.

PY - 2024

Y1 - 2024

N2 - The correlation gap of a real-valued set function f : 2N → 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 − √21πℓ 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.

AB - The correlation gap of a real-valued set function f : 2N → 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 − √21πℓ 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.

UR - http://www.scopus.com/inward/record.url?scp=85194170499&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85194170499&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85194170499

T3 - 2024 Symposium on Simplicity in Algorithms, SOSA 2024

SP - 396

EP - 405

BT - 2024 Symposium on Simplicity in Algorithms, SOSA 2024

A2 - Parter, Merav

A2 - Pettie, Seth

PB - Society for Industrial and Applied Mathematics Publications

T2 - 7th SIAM Symposium on Simplicity in Algorithms, SOSA 2024

Y2 - 8 January 2024 through 10 January 2024

ER -