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\).

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