Abstract:

This paper deals with a general variant of the reverse undesirable (obnoxious) center location problem on cycle graphs. Given a ‘selective’ subset of the vertices of the underlying cycle graph as location of the existing customers, the task is to modify the edge lengths within a given budget such that the minimum of distances between a predetermined undesirable facility location and the customer points is maximized under the perturbed edge lengths. We develop a combinatorial O(n log n) algorithm for the problem with continuous modifications. For the uniform-cost model, we solve this problem in linear time by an improved algorithm. Furthermore, exact solution methods are proposed for the problem with integer modifications.

Key words: Undesirable center location ·, Reverse optimization ·, Combinatorial optimization ·, Time complexity