Matroid Contention Resolution with Concentration
cs.DS, math.CO
Submitted: 2026-07-10
Updated: 2026-07-10
License: http://creativecommons.org/licenses/by/4.0/
The gist: Contention resolution schemes (CRS) are a fundamental and widely applied tool for rounding fractional solutions subject to combinatorial constraints.
Terminology
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 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 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 k) -approximation for k-matroid intersection coloring (improving the prior O(k 2)) when the chromatic number of at least one matroid is Ω(k cubed 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.
Sources
- Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture
- Efficiently Coloring the Intersection of a General Matroid and Combinatorial Matroids
Related papers
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles