Random order contention resolution schemes

DOI10.1109/FOCS.2018.00080MaRDI QIDQ6944332zbMATH OpenFDO

Authors Marek Adamczyk, Michał Włodarczyk

Publication date 12 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2018.00080

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cited in

(11)

• The outer limits of contention resolution on matroids and connections to the secretary problem
• Simple and optimal online contention resolution schemes for k-uniform matroids
• From contention resolution to matroid secretary and back
• Online contention resolution schemes for size-stochastic knapsacks
• Towards an optimal contention resolution scheme for matchings
• Online combinatorial assignment in independence systems
• Pairwise-independent contention resolution
• Delegated stochastic probing
• Online combinatorial assignment in independence systems
• Pairwise-independent contention resolution
• Random order vertex arrival contention resolution schemes for matching, with applications

This page was built for publication: Random order contention resolution schemes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6944332)