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


الملخص بالإنكليزية

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)$.

تحميل البحث