Matching on the Line Admits no \(o(\sqrt {\log n})\) -Competitive Algorithm
Enoch Peserico, Michele Scquizzato · ACM Transactions on Algorithms · 2023
We present a simple proof that no randomized online matching algorithm for the line can be \((\sqrt {\log _2(n+1)}/15)\) -competitive against an oblivious adversary for any n = 2 i - 1 : i ∈ ℕ. This is the first super-constant lower bound for the problem, and disproves as a corollary a recent conjecture on the topology-parametrized competitiveness achievable on generic spaces.