3 citations · 5 across the 10 of their papers we have counts for
8 papers · 1 filter
Dynamic Matching with Abandonment: Optimal Guarantees via Static Priority Policies
Nick Arnosti, Rad Niazadeh, Pranav Nuti +1
We study stochastic dynamic matching with abandonment, a fundamental model in which agents of different types arrive over time, may abandon the market while waiting, and can be mat…
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…
Online Matching and Contention Resolution for Edge Arrivals with Vanishing Probabilities
Will Ma, Calum MacRury, Pranav Nuti
We study the performance of sequential contention resolution and matching algorithms on random graphs with vanishing edge probabilities. When the edges of the graph are processed i…
Prophet Inequalities with Cancellation Costs
Farbod Ekbatani, Rad Niazadeh, Pranav Nuti +1
Most of the literature on online algorithms and sequential decision-making in revenue management focuses on settings with irrevocable decisions. Motivated by modern applications su…
A Tight Competitive Ratio for Online Submodular Welfare Maximization
Amit Ganz, Pranav Nuti, Roy Schwartz
In this paper we consider the online Submodular Welfare (SW) problem. In this problem we are given bidders each equipped with a general (not necessarily monotone) submodular ut…
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}_…
The Secretary Problem with Distributions
Pranav Nuti
We study a variant of the secretary problem where candidates come from independent, not necessarily identical distributions known to us, and show that we can do at least as well as…