SOME VARIANTS OF REVERSE SELECTIVE CENTER LOCATION PROBLEM ON TREES UNDER THE CHEBYSHEV AND HAMMING NORMS

Abstract

This paper is concerned with two variants of the reverse selective center location problems on tree graphs under the Hamming and Chebyshev cost norms in which the customers are existing on a selective subset of the vertices of the underlying tree. The first model aims to modify the edge lengths within a given modification budget until a prespecified facility location becomes as close as possible to the customer points. However, the other model wishes to change the edge lengths at the minimum total cost so that the distances between the prespecified facility and the customers satisfy a given upper bound. We develop novel combinatorial algorithms with polynomial time complexities for deriving the optimal solutions of the problems under investigation.