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

Chandra Chekuri, Junkai Song, Weizhong Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2024 Symposium on Simplicity in Algorithms, SOSA 2024
EditorsMerav Parter, Seth Pettie
PublisherSociety for Industrial and Applied Mathematics Publications
Pages396-405
Number of pages10
ISBN (Electronic)9781713887171
StatePublished - 2024
Event7th SIAM Symposium on Simplicity in Algorithms, SOSA 2024 - Alexandria, United States
Duration: Jan 8 2024Jan 10 2024

Publication series

Name2024 Symposium on Simplicity in Algorithms, SOSA 2024

Conference

Conference7th SIAM Symposium on Simplicity in Algorithms, SOSA 2024
Country/TerritoryUnited States
CityAlexandria
Period1/8/241/10/24

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Fingerprint

Dive into the research topics of 'Contention Resolution for the ℓ-fold union of a matroid via the correlation gap'. Together they form a unique fingerprint.

Cite this