Computational comparison of two algorithms for the Euclidean single facility location problem

The best known first order and second order methods for the Euclidean single facility location problem are Weiszfeld's algorithm and Newton's algorithm, respectively. With only a linear rate of convergence, Weiszfeld's algorithm is a simple closed form iteration formula. With a quadratic rate of convergence, Newton's algorithm is more complicated and requires a line search at each iteration. In this paper, computational comparisons were made between these two algorithms. Both sequential and parallel versions of each algorithm were compared. These results show that the second order method is more efficient for low dimensional problems while the first order method is more efficient for high dimensional problems. A parallel version of each algorithm was implemented on a NCUBE hypercube with 64 processors and tested on randomly generated problems with space dimension from 2 to 9, and the number of existing facilities from 1000 to 9000. A speedup of as high as 58 was achieved with 64 processors.