The p-center problem in \(R^ n\) with weighted Tchebycheff norms. (English) Zbl 0747.90059

Pelegrin Pelegrin, Blas

Belg. J. Oper. Res. Stat. Comput. Sci. 31, No. 1-2, 49-62 (1991).

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

Keywords:

\(p\)-center problem; weighted Tchebycheff norm; lower bound; unweighted rectangular \(p\)-center problem; 2-approximation heuristic polynomial algorithm