Grid based online algorithms for clustering problems
Gabriella Divéki, Csanád Imreh · 2014
In this paper we consider the online variable sized clustering problem in d-dimensional Euclidean spaces where the cost of a cluster depends on the p-th power of its side. The previous results are extended from the model with square cost in 2-dimensional spaces. We determine the competitive ratio of the algorithm GRID in the general case. We show that it is not constant competitive if pd-competitive if p≥d. In 2-dimensional space we analyze a more sophisticated algorithm called ShiftGrid and prove that it is 7-competitive for the best choice of its parameter.