Rob van Stee
March 28, 2007
Title:
On the online unit clustering problem
Abstract: We continue the study of the online unit clustering problem, introduced by Chan and Zarrabi-Zadeh (\emph{Workshop on Approximation and Online Algorithms 2006}, p.121-131). We design a deterministic algorithm with a competitive ratio of $7/4$ for the one-dimensional case. This is the first deterministic algorithm that beats the bound of 2. It also has a better competitive ratio than the previous randomized algorithm. Moreover, we provide the first non-trivial deterministic lower bound, which is 1.6.
Joint work with Lea Epstein.