2 citations · 4 across the 3 of their papers we have counts for
4 papers
Improved Online Contention Resolution for Matchings and Applications to the Gig Economy
Tristan Pollner, Mohammad Roghani, Amin Saberi +1
Motivated by applications in the gig economy, we study approximation algorithms for a \emph{sequential pricing problem}. The input is a bipartite graph between individu…
Decentralized Matching in a Probabilistic Environment
Mobin Y. Jeloudar, Irene Lo, Tristan Pollner +1
We consider a model for repeated stochastic matching where compatibility is probabilistic, is realized the first time agents are matched, and persists in the future. Such a model h…
Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities
Christos Papadimitriou, Tristan Pollner, Amin Saberi +1
The rich literature on online Bayesian selection problems has long focused on so-called prophet inequalities, which compare the gain of an online algorithm to that of a "prophet" w…
New Query Lower Bounds for Submodular Function MInimization
Andrei Graur, Tristan Pollner, Vidhya Ramaswamy +1
We consider submodular function minimization in the oracle model: given black-box access to a submodular set function , find an element of $\arg\mi…