Online Preemptive Matching Revisited
TL;DR
This result is the first result which shows hardness for instances where the optimal algorithm employs preemption, and improves upon the strongest previously known upper bound of $2-\sqrt{2} \approx 0.585$.
Abstract
We study the online preemptive matching problem, in which the edges of a graph arrive sequentially and the algorithm must maintain a matching by accepting or rejecting arriving edges and possibly discarding previously accepted ones. We prove a new upper bound of $0.5661$ on the competitive ratio achievable for the problem. This bound applies to arbitrary randomized algorithms, bipartite graphs and if we allow the algorithm to output a fractional solution. Our result improves upon the strongest previously known upper bound of $2-\sqrt{2} \approx 0.585$, due to Huang et al. [SODA'19]. Previous hardness constructions relied on edge sequences described by vertex arrivals where each arriving vertex reveals its edges to yet unvaried vertices. Under such sequences, Huang et al. showed that there exists a non-preemptive online algorithm with competitive ratio $\sim0.567$ (or $2-\sqrt{2}$ for fractional solutions). Consequently, our hardness construction is the first result which shows hardness for instances where the optimal algorithm employs preemption.