3 citations · 3 across the 7 of their papers we have counts for
4 papers · 1 filter
Online Matroid Embeddings
Andrés Cristi, Paul Dütting, Robert Kleinberg +2
We introduce the notion of an online matroid embedding, which is an algorithm for mapping an unknown matroid that is revealed in an online fashion to a larger-but-known matroid. We…
Prophet Inequalities Require Only a Constant Number of Samples
Andrés Cristi, Bruno Ziliotto
In a prophet inequality problem, independent random variables are presented to a gambler one by one. The gambler decides when to stop the sequence and obtains the most recent v…
Trading Prophets
José Correa, Andrés Cristi, Paul Dütting +3
In this work we initiate the study of buy-and-sell prophet inequalities. We start by considering what is arguably the most fundamental setting. In this setting the online algorithm…
The Two-Sided Game of Googol and Sample-Based Prophet Inequalities
José Correa, Andrés Cristi, Boris Epstein +1
The secretary problem or the game of Googol are classic models for online selection problems that have received significant attention in the last five decades. We consider a varian…