##
**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 |