17 citations · 95 across the 34 of their papers we have counts for
4 papers · 1 filter
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…
Fully Online Matching II: Beating Ranking and Water-filling
Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu +1
Karp, Vazirani, and Vazirani (STOC 1990) initiated the study of online bipartite matching, which has held a central role in online algorithms ever since. Of particular importance a…
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…
A Simple 1-1/e Approximation for Oblivious Bipartite Matching
Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang
We study the oblivious matching problem, which aims at finding a maximum matching on a graph with unknown edge set. Any algorithm for the problem specifies an ordering of the verte…