An improvement and an extension of the Elzinga & Hearn's algorithm to the 1-center problem in ?n withl 2b-normswithl 2b-norms

Summary In this paper we deal with the 1-center problem in ℝⁿ when the distance is measured by anyl _2b-norm. This type of norm generalizes the Euclidean norm (l ₂-norm) and can be used to estimate road distances or travel times in Locational Analysis, and to measure dissimilarities between data in Cluster Analysis. The problem is to find the smallestb-ellipsoid containing a given finite setA of points in ℝⁿ, which generalizes the one of finding the smallest sphere containingA (1-center problem with thel ₂-norm). We show that this problem has a unique optimal solution. For thel ₂-norm, we use the Elzinga-Hearn algorithm. New starting rules are proposed to initialize and to improve the algorithm. On the other hand, the Elzinga-Hearn algorithm is extended to solve the problem withl _2b-norms. Computational results are given for six differentl _2b-norms, when these new starting rules are used in order to show which is the best starting rule. Problems of up to 5.000 points in ℝⁿ,n=2,4,6,8 and 10, are solved in a few seconds.