zbMATH — the first resource for mathematics

The p-center problem in $$R^ n$$ with weighted Tchebycheff norms. (English) Zbl 0747.90059
Summary: The $$p$$-center problem in $$R^ n$$ 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 P. M. Dearing and R. L. Francis [Transport. Sci. 8, 333-343 (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 Y. P. Aneja, R. Chandrasekaran and K. P. K. Nair [Eur. J. Oper. Res. 35, No. 1, 118-123 (1988; Zbl 0699.90028)] 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 $$\delta<2$$ the existence of a $$\delta$$-approximation polynomial algorithm would imply that $$P=NP$$.

MSC:
 90B85 Continuous location 90-08 Computational methods for problems pertaining to operations research and mathematical programming 90C60 Abstract computational complexity for mathematical programming problems