Metraipolis › archive › dc_088d4e99f0a7

Dynamic Contention Resolution Schemes — arXiv:2609.21993

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.21993
License (as archived)
CC0-1.0
Archived
2026-10-10T02:48:03.294Z
SHA-256 of the archived text
49200e80cfd0ec6533ae1706239c51816399421381eab74670c8bde05d0b0a8d
Stable URL of this page
https://metraipolis.com/documento/dc_088d4e99f0a7

How to cite

Dynamic Contention Resolution Schemes — arXiv:2609.21993 — arXiv (en), https://arxiv.org/abs/2609.21993 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_088d4e99f0a7 (Metraipolis archive dc_088d4e99f0a7, sha256 49200e80cfd0ec6533ae1706239c51816399421381eab74670c8bde05d0b0a8d)
BibTeX
@misc{dc088d4e99f0a7,
  title = {Dynamic Contention Resolution Schemes — arXiv:2609.21993},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.21993},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_088d4e99f0a7; sha256 49200e80cfd0ec6533ae1706239c51816399421381eab74670c8bde05d0b0a8d},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.21993. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We introduce a low-recourse rounding paradigm for packing problems in fully dynamic settings, which we name Dynamic Contention Resolution Schemes (DCRSs). These are dynamic analogs of (Online) Contention Resolution Schemes (or (O)CRSs) for low-recourse dynamic optimization and offer a variety of benefits. Similarly to their offline and online counterparts, DCRSs for different constraints can be combined to obtain DCRSs for the constraints' intersection. Furthermore, together with the Positive Body Chasing framework of Bhattacharya, Buchbinder, Levin, and Saranurak [FOCS 2023], DCRSs imply competitive recourse algorithms for fully dynamic packing problems with submodular objectives: these are algorithms that, for any input sequence, incur recourse that is itself competitive with the best possible recourse for that sequence. We show the existence of $\Omega(1)$-balanced and $O(\log \mathrm{rank})$-recourse DCRSs for matroid constraints, and $\Omega(1)$-balanced/$O(1)$-recourse DCRSs for matching and knapsack constraints. In particular, these yield the first non-trivial recourse bound for fully dynamic knapsack, as well as the first competitive-recourse algorithm for non-bipartite matching, and both of these apply even to monotone submodular objectives. Beyond our particular results, we view the DCRS framework as a principled step towards mechanizing the relax-and-round paradigm of approximation algorithms in the context of dynamic optimization.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-21 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.21993 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T02:29:43.014Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-21?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).