Grid based online algorithms for clustering problems

摘要

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 p <; d and it is 3-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.