  The online unit clustering problem was proposed by Chan and Zarrabi-Zadeh
(WAOA2007 and Theory of Computing Systems 45(3), 2009), which is defined as
follows: "Points" are given online in the $d$-dimensional Euclidean space one
by one. An algorithm creates a "cluster," which is a $d$-dimensional rectangle.
The initial length of each edge of a cluster is 0. An algorithm can extend an
edge until it reaches unit length independently of other dimensions. The task
of an algorithm is to cover a new given point either by creating a new cluster
and assigning it to the point, or by extending edges of an existing cluster
created in past times. The goal is to minimize the total number of created
clusters. Chan and Zarrabi-Zadeh proposed some method to obtain a competitive
algorithm for the $d$-dimensional case using an algorithm for the
one-dimensional case, and thus the one-dimensional case has been extensively
studied including some variants of the unit clustering problem. 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$, and conjectured that the exact competitive
ratio in the one-dimensional case may be $13/8$.
