2023/09/26 by Nagy-György, Judit
#68W27 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2309.14730
In online unit clustering, points of a metric space arriving one by one must be partitioned into clusters of diameter at most 1, where the cost is the number of clusters. This paper gives linear upper and lower bounds on the advice complexity of 1-competitive online unit clustering algorithms, in terms of the number of points in ℝd and ℤd.