2015/02/09 by Jun Kawahara, Kawahara, Jun, Koji Kobayashi +2
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.1502.02422
5 pages
arxiv created 2015/02/09 · openalex publication_date 2015/02/09 · arxiv updated 2015/02/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.