research
∙
07/15/2022
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time
We present dynamic algorithms with polylogarithmic update time for estim...
share
research
∙
07/22/2021
The Stationary Prophet Inequality Problem
We study a continuous and infinite time horizon counterpart to the class...
research
∙
05/14/2021
The Greedy Algorithm is not Optimal for On-Line Edge Coloring
Nearly three decades ago, Bar-Noy, Motwani and Naor showed that no onlin...
research
∙
04/08/2021
Universally-Optimal Distributed Algorithms for Known Topologies
Many distributed optimization algorithms achieve existentially-optimal r...
research
∙
11/13/2019
Rounding Dynamic Matchings Against an Adaptive Adversary
We present a new dynamic matching sparsification scheme. From this schem...
research
∙
04/19/2019
Tight Bounds for Online Edge Coloring
Vizing's celebrated theorem asserts that any graph of maximum degree Δ a...
research
∙
11/06/2017
