60 citations · 237 across the 39 of their papers we have counts for
5 papers · 1 filter
Online Ordinal Problems: Optimality of Comparison-based Algorithms and their Cardinal Complexity
Nick Gravin, Enze Sun, Zhihao Gavin Tang
We consider ordinal online problems, i.e., tasks that only require pairwise comparisons between elements of the input. A classic example is the secretary problem and the game of go…
Secretary Matching with General Arrivals
Tomer Ezra, Michal Feldman, Nick Gravin +1
We provide online algorithms for secretary matching in general weighted graphs, under the well-studied models of vertex and edge arrivals. In both models, edges are associated with…
Online Stochastic Max-Weight Matching: prophet inequality for vertex and edge arrival models
Tomer Ezra, Michal Feldman, Nick Gravin +1
We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arriv…
Online Stochastic Matching with Edge Arrivals
Nick Gravin, Zhihao Gavin Tang, Kangning Wang
Online bipartite matching with edge arrivals remained a major open question for a long time until a recent negative result by [Gamlath et al. FOCS 2019], who showed that no online…
On the Continuous CNN Problem
John Augustine, Nick Gravin
In the (discrete) CNN problem, online requests appear as points in . Each request must be served before the next one is revealed. We have a server that can serve a re…