Open Research Index

Matroid Contention Resolution with Concentration

Stephen Arndt, Benjamin Moseley, Kirk Pruhs, Michael Zlatin

arXivarxiv/2607.09268Jul 10, 2026cs.DSscore 0

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,…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2607.09268
curl -X POST /api/v1/records/arxiv/2607.09268/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.09268/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'