English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Random order online contention resolution schemes (ROCRS) are structuredonline rounding algorithms with numerous applications and links to otherwell-known online selection problems, like the matroid secretary conjecture. Weare interested in ROCRS subject to a matroid constraint, which is among themost studied constraint families. Previous ROCRS required to know upfront thefull fractional point to be rounded as well as the matroid. It is unclear towhat extent this is necessary. Fu, Lu, Tang, Turkieltaub, Wu, Wu, and Zhang(SOSA 2022) shed some light on this question by proving that no strong(constant-selectable) online or even offline contention resolution schemeexists if the fractional point is unknown, not even for graphic matroids.  In contrast, we show, in a setting with slightly more knowledge and where thefractional point reveals one by one, that there is hope to obtain strong ROCRSby providing a simple constant-selectable ROCRS for graphic matroids that onlyrequires to know the size of the ground set in advance. Moreover, our procedureholds in the more general adversarial order with a sample setting, where, aftersampling a random constant fraction of the elements, all remaining(non-sampled) elements may come in adversarial order.

Simple Random Order Contention Resolution for Graphic Matroids with Almost no Prior Information