{"id":"arxiv/2607.09268","url":"https://arxiv.org/abs/2607.09268","tags":["cs.DS","math.CO"],"score":0,"title":"Matroid Contention Resolution with Concentration","domain":"cs.DS","source":"arxiv","authors":["Stephen Arndt","Benjamin Moseley","Kirk Pruhs","Michael Zlatin"],"reviews":0,"subject":"cs.DS","summary":"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,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-10","reactions":{}}