Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Prophet Inequalities and Online Contention Resolution for Matchoids
Calum MacRury, Pranav Nuti, Jan Vondrák
In the classical prophet inequality, an algorithm observes a sequence of random variables with known distributions in an online fashion, and it must select one of the random variab…
cs.DS2022
Towards an Optimal Contention Resolution Scheme for Matchings
Pranav Nuti, Jan Vondrák
In this paper, we study contention resolution schemes for matchings. Given a fractional matching and a random set where each edge appears independently with probabil…
cs.DS2022
Secretary Problems: The Power of a Single Sample
Pranav Nuti, Jan Vondrák
In this paper, we investigate two variants of the secretary problem. In these variants, we are presented with a sequence of numbers that come from distributions $\mathcal{D}_…