The P-Center problem in Rᴺ with weighted Tchebycheff norms

Abstract

In this paper the p-center problem in R" 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 (1974) 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. (1988) 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 6<2 the existence of a d-approximation polynomial algorithm would imply that P= NP.