English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The online unit clustering problem was proposed by Chan and Zarrabi-Zadeh(WAOA2007 and Theory of Computing Systems 45(3), 2009), which is defined asfollows: "Points" are given online in the $d$-dimensional Euclidean space oneby 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 anedge until it reaches unit length independently of other dimensions. The taskof an algorithm is to cover a new given point either by creating a new clusterand assigning it to the point, or by extending edges of an existing clustercreated in past times. The goal is to minimize the total number of createdclusters. Chan and Zarrabi-Zadeh proposed some method to obtain a competitivealgorithm for the $d$-dimensional case using an algorithm for theone-dimensional case, and thus the one-dimensional case has been extensivelystudied 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 anydeterministic online algorithm for the one-dimensional unit clustering,improving the previous lower bound $8/5 (=1.6)$ presented by Epstein and vanStee (WAOA2007 and ACM Transactions on Algorithms 7(1), 2010). Note that Ehmsenand Larsen (SWAT2010 and Theoretical Computer Science, 500, 2013) showed thecurrent best upper bound of $5/3$, and conjectured that the exact competitiveratio in the one-dimensional case may be $13/8$.

An improved lower bound for one-dimensional online unit clustering