Many heuristic algorithms have been proposed in the literature for the solution of p-center problems, most of which can be used in any metric space. However, little computational experience has been reported with these heuristics, most times for problems in ℝ2 with the Euclidean distance. In this paper, the authors consider the unweighted p-center problem in ℝ’m when distance is measured by the Tchebycheff norm, which they name the Rectangular p-Cover Problem. The authors propose new heuristic algorithms for this problem, and present computational results. Firstly, a new class of heuristics based on the generation of seed points is given, which is obtained using a new assignment rule. Secondly, two new algorithms based on partitions are given, which can be seen as heuristics of improvement type. Finally, it is shown by computational experiments that the new algorithms improve some other related heuristics considered in this paper.
