10 citations · 23 across the 21 of their papers we have counts for
6 papers · 1 filter
The Stationary Prophet Inequality Problem
Kristen Kessel, Amin Saberi, Ali Shameli +1
We study a continuous and infinite time horizon counterpart to the classic prophet inequality, which we term the stationary prophet inequality problem. Here, copies of a good arriv…
Beating the Folklore Algorithm for Dynamic Matching
Mohammad Roghani, Amin Saberi, David Wajc
The maximum matching problem in dynamic graphs subject to edge updates (insertions and deletions) has received much attention over the last few years; a multitude of approximation/…
Lossless Online Rounding for Online Bipartite Matching (Despite its Impossibility)
Niv Buchbinder, Joseph, Naor +1
For numerous online bipartite matching problems, such as edge-weighted matching and matching under two-sided vertex arrivals, the state-of-the-art fractional algorithms outperform…
The Greedy Algorithm is \emph{not} Optimal for On-Line Edge Coloring
Amin Saberi, David Wajc
Nearly three decades ago, Bar-Noy, Motwani and Naor showed that no online edge-coloring algorithm can edge color a graph optimally. Indeed, their work, titled "the greedy algorithm…
Universally-Optimal Distributed Algorithms for Known Topologies
Bernhard Haeupler, David Wajc, Goran Zuzic
Many distributed optimization algorithms achieve existentially-optimal running times, meaning that there exists some pathological worst-case topology on which no algorithm can do b…
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…