We present new relaxation algorithms for the uncapacitated continuous and discrete p-center problems. We have conducted an experimental study that demonstrated that these new algorithms are extremely efficient. © 2008 Elsevier Ltd. All rights reserved.