2 citations · 5 across the 8 of their papers we have counts for
9 papers
Optimal Rounding for Two-Stage Bipartite Matching
Tristan Pollner, Amin Saberi, Anders Wikum
We study two-stage bipartite matching, in which the edges of a bipartite graph on vertices are revealed in two batches. In stage one, a matching must be selecte…
A Bicriterion Concentration Inequality and Prophet Inequalities for -Fold Matroid Unions
Noga Alon, Nick Gravin, Tristan Pollner +4
We investigate prophet inequalities with competitive ratios approaching , seeking to generalize -uniform matroids. We first show that large girth does not suffice: for all $k…
Improved Approximations for Stationary Bipartite Matching: Beyond Probabilistic Independence
Alireza AmaniHamedani, Ali Aouad, Tristan Pollner +1
We study stationary online bipartite matching, where both types of nodes--offline and online--arrive according to Poisson processes. Offline nodes wait to be matched for some rando…
New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling
Mark Braverman, Mahsa Derakhshan, Tristan Pollner +2
We study the polynomial-time approximability of the optimal online stochastic bipartite matching algorithm, initiated by Papadimitriou et al. (EC'21). Here, nodes on one side of th…
Approximating Optimum Online for Capacitated Resource Allocation
Alexander Braun, Thomas Kesselheim, Tristan Pollner +1
We study online capacitated resource allocation, a natural generalization of online stochastic max-weight bipartite matching. This problem is motivated by ride-sharing and Internet…
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…