A rounding and clustering-based exact algorithm for the p-center problem

The p-center problem consists of selecting p facilities from a set of possible sites and allocating a set of clients to them in such a way that the maximum distance between a client and the facility to which it is allocated is minimized. This paper proposes a new scalable exact solution algorithm based on client clustering and an iterative distance rounding procedure. The client clustering enables to initialize and update a subset of clients for which the p-center problem is iteratively solved. The rounding drastically reduces the number of distinct distances considered at each iteration. Our algorithm is tested on 396 benchmark instances with up to 1.9 million clients and facilities. Our results show that our approach outperforms existing methods run on the same computer except when p is smaller than 5. In this case, however, we optimally solve all instances in less than 2 min on average.