3 citations · 4 across the 4 of their papers we have counts for
3 papers · 1 filter
Graphic Matroid Secretary without the Graph
Paul Dütting, Renato Paes Leme, Martin Pál +1
The matroid secretary problem (MSP) is one of the cleanest, and most captivating open problems in online algorithms. The famous MSP conjecture stipulates that there exists a consta…
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…
On Sparsification of Stochastic Packing Problems
Shaddin Dughmi, Yusuf Hakan Kalayci, Neel Patel
Motivated by recent progress on stochastic matching with few queries, we embark on a systematic study of the sparsification of stochastic packing problems (SPP) more generally. Spe…