19 citations · 74 across the 51 of their papers we have counts for
12 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…
Combinatorial Optimization using Comparison Oracles
Vincent Cohen-Addad, Tommaso d'Orsi, Anupam Gupta +7
In linear combinatorial optimization, we aim to find for a family over a ground set…
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…
Bernoulli Factories for Flow-Based Polytopes
Rad Niazadeh, Renato Paes Leme, Jon Schneider
We construct explicit combinatorial Bernoulli factories for the class of \emph{flow-based polytopes}; integral 0/1-polytopes defined by a set of network flow constraints. This gene…
Secretaries with Advice
Paul Dütting, Silvio Lattanzi, Renato Paes Leme +1
The secretary problem is probably the purest model of decision making under uncertainty. In this paper we ask which advice can we give the algorithm to improve its success probabil…
Combinatorial Bernoulli Factories
Rad Niazadeh, Renato Paes Leme, Jon Schneider
A Bernoulli factory is an algorithmic procedure for exact sampling of certain random variables having only Bernoulli access to their parameters. Bernoulli access to a parameter $p…