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

Kangning Wang

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…