In this paper, the p-center problem in Rn is studied when distances are measured by a weighted Tchebycheff norm. For the 1-center problem it is proved that the lower bound proposed by Dearing and Francis is attained and a one step algorithm is given to obtain an optimal solution. Then, an exact algorithm for p>1 is proposed which generalizes the one given by Aneja et al. for the unweighted rectangular p-center problem on the plane. Finally, a new 2-approximation heuristic polynomial algorithm is given which is ‘best possible’ since for δ<2 the existence of a δ-approximation polynomial algorithm would imply that P=NP.
