A new assignment rule to improve seed points algorithms for the continuous k-center problem

摘要

Due to its complexity, the k-center problem cannot be solved exactly when the number of points is high enough. So, heuristic algorithms must be used to find good solutions for this location-allocation problem. The allocation part of the heuristics given in the literature consists of assigning each given point to its nearest center. In this paper, we propose a new assignment rule (NAR), from which a new class of seed points algorithms is obtained for the k-center problem in R~n. The new class differs from the usual class of seed points algorithms in the way the points are assigned to each seed point. Different methods to generate seed points are shown from which different algorithms are given by using the two assignment rules, the classical and the new. Most of these algorithms have linear complexity in the number of points and generate solutions with objective values within two times the optimal value, and all of them run very quickly and can be used for any metric. It is shown by computational experience that the running times and the quality of the solutions generated are notably improved by using the NAR.