Combinatorial Algorithms for Reverse Selective Undesirable Center Location Problems on Cycle Graphs

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.