Computer Science Colloquium, 2006-2007

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.


Benny Pinkas