Search

We consider the one-dimensional version of the online unit clustering problem, proposed by Chan and Zarrabi-Zadeh (WAOA2007 and Theory of Computing Systems 45(3), 2009), which is defined as follows: “Points” are given online on the line one by one. An algorithm creates a “cluster,” which is a line segment. The initial length of a cluster is 0, and an algorithm can extend a cluster until it reaches unit length. The task of an algorithm is to cover a new given point either by creating a new cluster and assigning the point to the cluster or by extending an existing cluster created in past times. The goal is to minimize the total number of created clusters. In this paper, we show a lower bound of 13 / 8 = 1.625 on the competitive ratio of any deterministic online algorithm for the one-dimensional unit clustering, improving the previous lower bound 8 / 5 ( = 1.6 ) presented by Epstein and van Stee (WAOA2007 and ACM Transactions on Algorithms 7(1), 2010). Note that Ehmsen and Larsen (SWAT2010 and Theoretical Computer Science, 500, 2013) showed the current best upper bound of 5/3. [ABSTRACT FROM AUTHOR]