1 citations · 2 across the 4 of their papers we have counts for
4 papers
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…
Online Matching: A Brief Survey
Zhiyi Huang, Zhihao Gavin Tang, David Wajc
Matching, capturing allocation of items to unit-demand buyers, or tasks to workers, or pairs of collaborators, is a central problem in economics. Indeed, the growing prevalence of…
Online Edge Coloring is (Nearly) as Easy as Offline
Joakim Blikstad, Ola Svensson, Radu Vintan +1
The classic theorem of Vizing (Diskret. Analiz.'64) asserts that any graph of maximum degree can be edge colored (offline) using no more than colors (with being a tri…
Simple and Asymptotically Optimal Online Bipartite Edge Coloring
Joakim Blikstad, Ola Svensson, Radu Vintan +1
We provide a simple online -edge-coloring algorithm for bipartite graphs of maximum degree under adversarial vertex arrivals on one side of the graph. Our…