Matching on the line admits no $o(\sqrt{\log n})$-competitive algorithm

Abstract

We present a simple proof that the competitive ratio of any randomized online matching algorithm for the line is at least $\sqrt{{\log }_2(n+1)}/12$ for all $n=2^i-1:i\in \mathbb{N}$.