Matroid Contention Resolution with Concentration
Abstract
Contention resolution schemes (CRS) are a fundamental and widely applied tool for rounding fractional solutions subject to combinatorial constraints. However, the known analyses of CRS generally only guarantee lower bounds on the expected value and concentration on the upper tail, but no concentration on the lower tail. Thus, CRS are generally not applicable to problems that contain covering constraints, since certifying a covering constraint holds requires a lower tail bound. Our main contribution is to derive lower tail bounds for the output of a particular contention resolution scheme, the random-order CRS of Adamczyk and Włodarczyk, which we call AW. We show that every linear function of the rounded solution attains a constant fraction of its expectation with a failure probability that is dimension-free, depending only on the expected value and on the number of matroids, but not on the size of the ground set. Our analysis is driven by a new property we call \emph{strong λ-boundedness}, which strengthens the known λ-boundedness of AW by providing two-sided control on how rounding propagates between elements. We then introduce a random process capturing AW, a \emph{sequential selection process}, that may be of independent interest. We prove lower tail bounds for any strongly λ-bounded sequential selection process. To demonstrate the applicability of our new tail bounds, we apply them to two problems involving covering constraints. The first result is an O(k log k)-approximation for k-matroid intersection coloring (improving the prior O(k2)) when the chromatic number of at least one matroid is Ω(k3 log n), where n is the number of elements. The second is the first bicriteria approximation algorithm for monotone submodular maximization under k matroid constraints together with packing and covering constraints.
Related
- A Better-Than-$3$ Approximation Algorithm for Demand Matching via Knapsack Intersection LP and Contention Resolution
- Suspense and surprise in matroid bingo
- A weighted inequality for matroid flats and log-concavity of Whitney numbers
- Condensed configurations and valuative matroid invariants
- Splitting the Matroid Determinant
BibTeX
@misc{arndt2026matroid,
title = {{Matroid Contention Resolution with Concentration}},
author = {Stephen Arndt and Benjamin Moseley and Kirk Pruhs and Michael Zlatin},
howpublished = {arXiv},
year = {2026},
month = jul,
doi = {10.48550/arxiv.2607.09268},
eprint = {2607.09268},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.09268},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Matroid Contention Resolution with Concentration
AU - Stephen Arndt
AU - Benjamin Moseley
AU - Kirk Pruhs
AU - Michael Zlatin
PY - 2026
DA - 2026/07/10
PB - arXiv
DO - 10.48550/arxiv.2607.09268
UR - https://arxiv.org/abs/2607.09268
AB - Contention resolution schemes (CRS) are a fundamental and widely applied tool for rounding fractional solutions subject to combinatorial constraints. However, the known analyses of CRS generally only guarantee lower bounds on the expected value and concentration on the upper tail, but no concentration on the lower tail. Thus, CRS are generally not applicable to problems that contain covering constraints, since certifying a covering constraint holds requires a lower tail bound. Our main contribution is to derive lower tail bounds for the output of a particular contention resolution scheme, the random-order CRS of Adamczyk and Włodarczyk, which we call AW. We show that every linear function of the rounded solution attains a constant fraction of its expectation with a failure probability that is dimension-free, depending only on the expected value and on the number of matroids, but not on the size of the ground set. Our analysis is driven by a new property we call \emph{strong λ-boundedness}, which strengthens the known λ-boundedness of AW by providing two-sided control on how rounding propagates between elements. We then introduce a random process capturing AW, a \emph{sequential selection process}, that may be of independent interest. We prove lower tail bounds for any strongly λ-bounded sequential selection process. To demonstrate the applicability of our new tail bounds, we apply them to two problems involving covering constraints. The first result is an O(k log k)-approximation for k-matroid intersection coloring (improving the prior O(k^2)) when the chromatic number of at least one matroid is Ω(k^3 log n), where n is the number of elements. The second is the first bicriteria approximation algorithm for monotone submodular maximization under k matroid constraints together with packing and covering constraints.
ER -