Answers are grounded in this paper and cite their sources.
We provide a simple (1-O(1√k))-selectable Online Contention Resolution Scheme for k-uniform matroids against a fixed-order adversary. If Aᵢ and Gᵢ denote the set of selected elements and the set of realized active elements among the first i (respectively), our algorithm selects with probability 1-1√k any active element i such that |Aᵢ₋₁| + 1 ≤ (1-1√k)· E[|Gᵢ|]+√k. This implies a (1-O(1√k)) prophet inequality against fixed-order adversaries for k-uniform matroids that is considerably simpler than previous algorithms [Ala14, AKW14, JMZ22]. We also prove that no OCRS can be (1-Ω(√log k/k))-selectable for k-uniform matroids against an almighty adversary. This guarantee is matched by the (known) simple greedy algorithm that accepts every active element with probability 1-Θ(√log k/k) [HKS07].
No takes yet. Share an insight, caveat, or question.
Dinev et al. (2023) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: