An $\Omega (\log n)$ Lower Bound for Online Matching on the Line

Abstract

For online matching with the line metric, we present a lower bound of $\Omega (\log n)$ on the approximation ratio of any online (possibly randomized) algorithm. This beats the previous best lower bound of $\Omega (\sqrt{\log n})$ and matches the known upper bound of $O(\log n)$.

There is a crucial error in the proof of Lemma 1, rendering the entire message invalid