4 papers
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…
Approximating Nash Social Welfare by Matching and Local Search
Jugal Garg, Edin Husić, Wenzheng Li +2
For any , we give a simple, deterministic -approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. We also co…
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…
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}_…